Method for generating prime numbers

Page 1 of 8 [ 113 posts ] Go to page 1, 2, 3, 4, 5 ... 8 Next

Previous topic | Next topic

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 1:31 am

I have devised a method for generating prime numbers. Is there one already in existence?

Chronos
Veteran
Veteran

Joined: 22 Apr 2010
Age: 44
Gender: Female
Posts: 8,698

13 Feb 2012, 1:50 am

jackmt wrote:

I have devised a method for generating prime numbers. Is there one already in existence?

There is no method to predict a prime number however there are ways to generate certain prime numbers.

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 1:51 am

Let n = 1.
Check if n is prime.
If n is prime, PRINT n.
Increase n by 1.
Repeat.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 1:52 am

Chronos wrote:

jackmt wrote:

I have devised a method for generating prime numbers. Is there one already in existence?

There is no method to predict a prime number however there are ways to generate certain prime numbers.

Can you briefly sketch a method? I believe my method will generate all of them.

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 1:54 am

jackmt wrote:

I believe my method will generate all of them.

I already provided a simple program that will generate all prime numbers. That's trivial.

The key point is: can you find large prime numbers fast?

Ellingtonia
Sea Gull

Joined: 9 Oct 2011
Age: 33
Gender: Male
Posts: 200

13 Feb 2012, 1:59 am

Post the method!

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 2:00 am

Declension wrote:

jackmt wrote:

I believe my method will generate all of them.

I already provided a simple program that will generate all prime numbers. That's trivial.

The key point is: can you find large prime numbers fast?

How large, how fast? A few minutes, hours, days? Can you use a computer? A very short program is required for my method.

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 2:05 am

jackmt wrote:

How fast? A few minutes, hours, days? can you use a computer?

The usual method has the following property: there is some positive number A such that the method can find all of the prime numbers from 1 to N in (A × N) seconds. Is your method faster than that?

EDIT: If you haven't thought about it much before, you might not have realised that it is a strange thing to talk about how "fast" you can do something that takes an infinite amount of time. No matter what method we use, it will take an infinite amount of time to find "all" of the prime numbers. So we measure how fast we can find all of the prime numbers from 1 to N, for any natural number N.

EDIT: You are of course correct that you will be able to implement any algorithm faster if you have a faster computer. However, using a thing called "Big-O notation", these differences do not actually matter. It's difficult to explain, maybe just post your method and we can talk about it?

Last edited by Declension on 13 Feb 2012, 2:11 am, edited 1 time in total.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 2:07 am

Declension wrote:

jackmt wrote:

How fast? A few minutes, hours, days? can you use a computer?

The usual method has the following property: there is some positive number A such that the method can find all of the prime numbers from 1 to N in (A × N) seconds. Is your method faster than that?

With a computer, I am sure it is. I will have to find it or rewrite it before I can post it. It is that simple.
And to what does "A" refer in "(A x N)?

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 2:15 am

jackmt wrote:

And to what does "A" refer in "(A x N)?

This topic is actually more confusing than it first appears. I'm not sure how to explain myself better without teaching you a course on algorithmics.

Here's the key: the important thing about an algorithm is not how long it takes on a specific computer, but how long it always takes in proportion to the problem size. The usual method (the Sieve of Eratosthenes) has the property that the amount of time taken is "directly proportional" to the problem size. (There are also faster methods, but they would be confusing to talk about.)

This means that no matter how slow or fast your computer is, there is some positive number A such that you can find all of the primes from 1 to N in under (A x N) seconds using the Sieve of Eratosthenes. The exact value of A will depend on how fast your computer is.

johnsmcjohn
Veteran
Veteran

Joined: 1 Jun 2011
Age: 43
Gender: Male
Posts: 1,279
Location: Las Vegas

13 Feb 2012, 2:15 am

The only reliable method of generating prime numbers is the sieve of Eratosthenes. Unfortunately it is hideously inefficient. Should you devise a method that reliably creates large(say over a million digits) primes, you'll probably win a Fields Medal. Good luck.

_________________
Your Aspie score: 181 of 200
Your neurotypical (non-autistic) score: 30 of 200
You are very likely an Aspie
Myers-Briggs: INTJ
AQ: 44

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 2:18 am

johnsmcjohn wrote:

you'll probably win a Fields Medal

Hah! More likely, he'll be whisked away by the CIA and nobody will ever see him again... :wink:

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 3:48 am

johnsmcjohn wrote:

My method is better and more efficient. It does involve a two step filter after generating "prime candidates." It sounds like it may be valuable. Who should I see?

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 3:51 am

jackmt wrote:

My method is better and more efficient.

There are actually known methods that are more efficient than the Sieve of Eratosthenes. They're just not much better.

Maybe you should use a sort of "meta" thinking to judge whether or not you are likely to have discovered something amazing. There are people who have spent their entire lives trying to find good algorithms for generating primes, and their best efforts would take many many pages to write out.

If your method is relatively simple, it is very likely that it is not as good as the best method known. So you shouldn't feel worried about sharing it with us. It's fun to talk about this stuff.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

13 Feb 2012, 3:55 am

Declension wrote:

jackmt wrote:

My method is better and more efficient.

What if I could generate an infinite number of primes from one prime almost instantly?
I looked up the Eratosthenes sieve, the Atkin(?) sieve, and the wheel sieve. They do not generate primes; they eliminate non-primes. I generate primes.

Last edited by jackmt on 13 Feb 2012, 4:03 am, edited 1 time in total.

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

13 Feb 2012, 4:01 am

jackmt wrote:

What if I could generate an infinite number of primes from one prime almost instantly?

That's logically impossible. A program cannot generate an infinite number of primes in a finite amount of time. Think about it. Everytime the program outputs a prime, it takes some time to do so.

Page 1 of 8 [ 113 posts ] Go to page 1, 2, 3, 4, 5 ... 8 Next

Jump to:

Method for generating prime numbers Post Reply New Topic

Method for generating prime numbers