Method for generating prime numbers - Computers, Math, Science, and Technology

WP Members: > 70,000

New Today: 8
New Yesterday: 31

Method for generating prime numbers

Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Wrong Planet Autism Forum Index -> Computers, Math, Science, and Technology

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2388

Posted: Sun Feb 19, 2012 6:54 pm Post subject:

Declension wrote:

The only two readings that I can think of are "In order to find all of the primes from 1 to N, you need to find all of the primes from 1 to N", which is trivial, and "In order to check whether N is a prime, you need to check whether every number below N is a prime", which is false.

Another might be: in order to find all the primes less than n, you either have to check whether any of the primes below sqrt(n) divides the number (without skipping any of the primes < sqrt(n)), or else you have to do something else that is at least as complicated.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1653

Posted: Sun Feb 19, 2012 7:05 pm Post subject:

Ancalagon wrote:

I guess you made a typo and actually meant: "in order to check whether n is prime, ..."

This is definitely a good reading. However, it isn't true, at least if "complicated" is measured in terms of asymptotic time complexity.

http://en.wikipedia.org/wiki/AKS_primality_test

This is a way to check whether or not a number is prime that is actually asymptotically quicker than finding out whether or not every number from 1 to sqrt(n) goes into n.

You talked about finding out whether every prime from one to sqrt(n) goes into n, as opposed to every number. But this is begging the question, isn't it? An algorithm for determining primality shouldn't already know which numbers are prime, that's cheating. Wink

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1653

Posted: Sun Feb 19, 2012 7:22 pm Post subject:

Wait, I just thought of a good reading for it! It's actually really simple.

What we are trying to say is:

Quote:

Let A be an algorithm (written using a finite number of lines of code, and without reference to an infinite database of prime numbers! Laughing

) that takes any natural number n and outputs whether or not n is prime. For any natural number n, let t(n) be the amount of steps it takes the algorithm to give us the answer for n. Then limsup_(n -> infinity)t(n) = infinity. In other words, for any large number K there is some natural number n such that t(n) > K.

In other words, it is generally easier to check the primality of small numbers than it is to check the primality of large ones.

I think that this statement is definitely true.

jackmt
Raven
Raven

Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT

Posted: Sun Feb 19, 2012 11:58 pm Post subject:

After discussing my method with someone tonight I was about to give up, thinking I was right at first to have thought it wasn't anything more than interesting. Then after awhile it occurred to me how to make it even simpler: generate any n length number x and check if it has the prime property. This can be done while the number is being generated. If so, check for prime factors 7 to x/14. If not, apply my trick and check for prime factors 7 to x/14. This will produce about n^2+n prime candidates, most of which (I believe about 88%. I will get back.) will be prime. Is this anything? Last edited by jackmt on Mon Feb 20, 2012 1:17 am; edited 3 times in total

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2388

Posted: Mon Feb 20, 2012 1:01 am Post subject:

Declension wrote:

I guess you made a typo and actually meant: "in order to check whether n is prime, ..."

Nope. I think a bit in the middle of what I said might have been unclear, but I was definitely talking about finding all primes < n.

Quote:

This is a way to check whether or not a number is prime that is actually asymptotically quicker than finding out whether or not every number from 1 to sqrt(n) goes into n.

If you used AKS to find them all from 2 to n, then you'd have AKS(2), AKS(3) ... AKS(n-1), AKS(n), which would probably be a lot slower.

Quote:

But this is begging the question, isn't it? An algorithm for determining primality shouldn't already know which numbers are prime, that's cheating. Wink

Yes, it is cheating. It's my favorite type of cheating: recursion. Cool

Say we want to build a function that returns every prime <= n. It will return a list of primes. We'll call it like this: list = primes(n). We'll write lists as something like this: [1,2,3], and empty lists as [].

For the algorithm, we'll just use what I suggested before, and we'll have a helper function indivisible(list, n) that returns true if none of the numbers in the list evenly divides n.

Code:

primes(n):
if (n < 2) then return []
let s = ceiling( sqrt(n) )
let list = primes(s)
for i = s+1 to n:
if indivisible(primes(s), i) then add i to list
return list

If we call primes(100), it calls primes(10), which calls primes(4), which calls primes(2), which calls primes(1), which returns an empty list. So primes(2) dutifully checks all numbers from 2 to 2 for any numbers in an empty list which evenly divide 2. Finding none, it puts 2 in the list and returns it. Then primes(4) checks from 3 to 4 using [2], and puts 3 in the list. Primes(10) checks from 5 to 10 using [2,3], and puts 5 and 7 in the list, which it hands to primes(100), which checks from 11 to 100 with the list [2,3,5,7], and gives us the list of primes we want.

Basically, it works because we're not asking for the whole list of primes, just a smaller sublist, and eventually you get down to a simple situation where you immediately know the answer. (An empty list contains every prime < 2)
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1653

Posted: Mon Feb 20, 2012 1:10 am Post subject:

Ancalagon wrote:

Nope. I think a bit in the middle of what I said might have been unclear, but I was definitely talking about finding all primes < n.

Sorry, I was on completely the wrong track then.

So what is your reading of the claim then? Something like, "Task (1.) is at least as hard as Task (2.), where the tasks are:
(1.) Find all primes from 1 to N.
(2.) Find out which primes go into N, given that you already know all the primes less than N."

This might be true, but how is it in the spirit of the original claim? It seems a bit arbitrary.

lau
Really nice person to know. :)
Phoenix

Joined: Jun 18, 2006
Age: 64
Posts: 10537
Location: Somerset UK

Posted: Mon Feb 20, 2012 3:23 am Post subject:

jackmt wrote:

... and check for prime factors 7 to x/14. ...

... and how would you do this?
_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer

NakaCristo
Tufted Titmouse

Joined: Jan 24, 2012
Age: 26
Posts: 49
Location: Santander, Spain

Posted: Mon Feb 20, 2012 3:55 am Post subject:

Ancalagon wrote:

Quote:

This is a way to check whether or not a number is prime that is actually asymptotically quicker than finding out whether or not every number from 1 to sqrt(n) goes into n.

If you used AKS to find them all from 2 to n, then you'd have AKS(2), AKS(3) ... AKS(n-1), AKS(n), which would probably be a lot slower.

No.

The only better than AKS which we know are probabilistic algorithms (which have their own problems).

Jono
Phoenix
Phoenix

Joined: Jul 11, 2008
Age: 33
Posts: 2884
Location: Johannesburg, South Africa

Posted: Mon Feb 20, 2012 3:56 am Post subject:

ruveyn wrote:

Thom_Fuleri wrote:

An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
A little algebra, however, soon explains why.

.

The narrows down where to look for primes. But it is not a prime generator. 6*8 + 1 = 7*7

ruveyn

If all prime numbers beside 2 and 3 can still be expressed that way though, could one not use that in combination with the Sieve of Eratosthenes to speed up the algorithm?

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Mon Feb 20, 2012 6:18 am Post subject:

Thom_Fuleri wrote:

Declension wrote:

heavenlyabyss wrote:

I vehemently disagree with this common conception that is random.

Nobody believes that the prime numbers are random! They are obviously deterministic.

But they are pseudorandom, in many senses. This isn't just an opinion, it has been proven.

Technically, they are emergent. That is, they are determined - but the only way to work them out is to go through from the beginning.

Okay, yes, you are right. Some people think they are random, but they obviously are not mathematicians!

I still think there should be some explicit formula to determine them, although the formula may be too complex to meaningful.

I did some further reading on Ramanujan today and the guy is absolutely brilliant. I wish I had his mind.

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2388

Posted: Mon Feb 20, 2012 8:49 am Post subject:

NakaCristo wrote:

Ancalagon wrote:

If you used AKS to find them all from 2 to n, then you'd have AKS(2), AKS(3) ... AKS(n-1), AKS(n), which would probably be a lot slower.

No.

The only better than AKS which we know are probabilistic algorithms (which have their own problems).

Can you prove this? (note: we're talking about finding all of them from 2 to n here, not just one number)

Declension wrote:

So what is your reading of the claim then?

That there is no significant shortcut to finding all the primes. If you want them all (up to n) then you have to start at the bottom and build up, and any other method will give up on certainty, or give up on getting them all, or end up doing at least as much work.

I don't have a proof of it, but I think it seems likely.

Jono wrote:

If all prime numbers beside 2 and 3 can still be expressed that way though, could one not use that in combination with the Sieve of Eratosthenes to speed up the algorithm?

From what I've been reading, it seems like something along these lines is standard practice. What I've read is a bit more complicated, it uses 30 (2*3*5), and adds 1, 7, 11, 13, 17, 19, 23, or 29 instead of 6 and 1 or 5.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

NakaCristo
Tufted Titmouse

Joined: Jan 24, 2012
Age: 26
Posts: 49
Location: Santander, Spain

Posted: Mon Feb 20, 2012 10:44 am Post subject:

Ancalagon wrote:

NakaCristo wrote:

Ancalagon wrote:

If you used AKS to find them all from 2 to n, then you'd have AKS(2), AKS(3) ... AKS(n-1), AKS(n), which would probably be a lot slower.

No.

The only better than AKS which we know are probabilistic algorithms (which have their own problems).

Can you prove this? (note: we're talking about finding all of them from 2 to n here, not just one number)

The following Maple code finds all primes using isprime, which is a probabilistic algorithm.

Quote:

n:=1;
count:=0;
while true do
if(isprime(n))then count:=count+1;fi;
n:=n+1;
od:
n,count;

In just a minute it has checked all <=13254203, which are exactly 864711 primes.

The complexity to get all primes <=n with this approach is O(n) calls to isprime, if isprime was AKS we would had O(n*log(n)^6), with Miller-Rabin (I assume that Maple use this) O(n*log(n)^2).
If isprime is simply check divisibility by all the previous n-1 numbers we would get O(n^2), if we only check up to sqrt(n) then O(n*sqrt(n))=O(n^(3/2)).
If we try to use the primes we have already calculated, dividing by them instead of dividing by all numbers, we would be diving by all primes <= than sqrt(n). Here appears the Prime-counting function pi(k)~k/ln(k), hence we would be checking divisibility by O(pi(sqrt(n)))=O(sqrt(n)/ln(sqrt(n)))=O(n^(1/2)/log n) for each number. Giving the total complexity of O(n^(3/2)/log n).
Since n^(1/2)/log n > log(n)^6 (for enough large n) we have that using AKS is better than simply dividing by the previous primes we have found.

With a Sieve of Eratosthenes approach we would get a block of n numbers (hence spatial complexity O(n), but that is another matter)
and then apply sieves.
The sieve by p requires looking O(n/p) ~ O(n) (as we use primes p<=sqrt(n)<<n).
We have a sieve for each prime p<=sqrt(n), this is pi(sqrt(n)) \in O(n^(1/2)/log n)
Again we have O(n^(3/2)/log n).

Shorttail
Blue Jay

Joined: Feb 04, 2012
Age: 26
Posts: 94
Location: Aarhus, Denmark

Posted: Mon Feb 20, 2012 5:44 pm Post subject:

ruveyn wrote:

Is there a computable function F such that F(n) is the n-th prime?

No. This is akin to the halting problem or the busy beaver, a non-computable function.

Jono wrote:

If all prime numbers beside 2 and 3 can still be expressed that way though, could one not use that in combination with the Sieve of Eratosthenes to speed up the algorithm?

The Sieve of Atkin is an optimized version. However, I have not been able to implement it in a manner that makes it faster than Sieve of Eratosthenes. On a boolean array in Java, Eratosthenes runs 2 billion in 38 seconds, 44 with a BitSet instead. Atkin runs slower. It does a number of wasteful calculations I haven't figured out how to ace faster.
If anyone knows how to bring down its running time (I heard it can be REALLY fast), please do share that knowledge.

heavenlyabyss wrote:

I still think there should be some explicit formula to determine them, although the formula may be too complex to meaningful.

I'm sure more than one mathematician lost their minds over this. Razz

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1653

Posted: Mon Feb 20, 2012 5:49 pm Post subject:

Ancalagon wrote:

But now it's back to the vague form in which it started. I can't make any rigorous sense out of this statement.

Ancalagon wrote:

I don't have a proof of it, but I think it seems likely.

Put it this way. If you did have a proof, what would the theorem be?

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2388

Posted: Mon Feb 20, 2012 9:41 pm Post subject:

NakaCristo wrote:

With a Sieve of Eratosthenes approach we would get a block of n numbers (hence spatial complexity O(n), but that is another matter)
and then apply sieves.
The sieve by p requires looking O(n/p) ~ O(n) (as we use primes p<=sqrt(n)<<n).
We have a sieve for each prime p<=sqrt(n), this is pi(sqrt(n)) \in O(n^(1/2)/log n)
Again we have O(n^(3/2)/log n).

This isn't wrong, since O() is an upper limit, but according to a couple of papers I've found, the Sieve of Eratosthenes runs in O(n) or O(n log log n). (I think the difference is a matter of an optimization being made or not.)

The Sieve of Atkin runs in O(n/log log n). So both of them are a bit faster than using AKS on every number less than n, but the small amount of difference surprised me.

Declension wrote:

If you did have a proof, what would the theorem be?

If we had the best single prime checker (call its running time s) and the best sieve prime checker (call its running time m), then for creating a list of all primes < n, m=O(s). In other words, they might be asymptotically the same, or s might be asymptotically slower.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Wrong Planet Autism Forum Index -> Computers, Math, Science, and Technology

Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Forums ©

Read more Articles on Wrong Planet

Wrong Planet is a Registered Trademark.
Copyright 2004-2013, Wrong Planet, LLC and Alex Plank. Alex does public speaking for Autism.

Advertise on Wrong Planet

Wrong Planet News Wrong Planet Forums