jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
 Posted: Mon Feb 13, 2012 1:31 am Post subject: Method for generating prime numbers |
 |
|
| I have devised a method for generating prime numbers. Is there one already in existence? |
|
| Back to top |
|
Chronos
Phoenix
Joined: Apr 23, 2010
Posts: 5231
|
| Posted: Mon Feb 13, 2012 1:50 am Post subject: Re: Method for generating prime numbers |
|
|
| 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. |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 1:51 am Post subject: |
|
|
Let n = 1.
Check if n is prime.
If n is prime, PRINT n.
Increase n by 1.
Repeat. |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Mon Feb 13, 2012 1:52 am Post subject: Re: Method for generating prime numbers |
|
|
| 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. |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 1:54 am Post subject: Re: Method for generating prime numbers |
|
|
| 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? |
|
| Back to top |
|
Ellingtonia
Pileated woodpecker
Joined: Oct 10, 2011
Age: 21
Posts: 186
|
| Posted: Mon Feb 13, 2012 1:59 am Post subject: |
|
|
| Post the method! |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Mon Feb 13, 2012 2:00 am Post subject: Re: Method for generating prime numbers |
|
|
| 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. |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 2:05 am Post subject: Re: Method for generating prime numbers |
|
|
| 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 Mon Feb 13, 2012 2:11 am; edited 1 time in total |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Mon Feb 13, 2012 2:07 am Post subject: Re: Method for generating prime numbers |
|
|
| 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)? |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 2:15 am Post subject: Re: Method for generating prime numbers |
|
|
| 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. |
|
| Back to top |
|
johnsmcjohn
ad hominem
Joined: Jun 02, 2011
Posts: 1213
Location: Las Vegas
|
| Posted: Mon Feb 13, 2012 2:15 am Post subject: |
|
|
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 |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 2:18 am Post subject: |
|
|
| 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...  |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Mon Feb 13, 2012 3:48 am Post subject: |
|
|
| johnsmcjohn wrote: | | 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. |
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? |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Mon Feb 13, 2012 3:51 am Post subject: |
|
|
| 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. |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Mon Feb 13, 2012 3:55 am Post subject: |
|
|
| Declension wrote: | | 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. |
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 Mon Feb 13, 2012 4:03 am; edited 1 time in total |
|
| Back to top |
|
  |
Wrong Planet Autism Forum Index
-> Computers, Math, Science, and Technology
|
1, 2, 3, 4, 5, 6, 7, 8 Next
|
|
|
