mersenneforum.org Need help with math problem re: searching for all primes.
 Register FAQ Search Today's Posts Mark Forums Read

 2003-06-08, 22:58 #1 daxm   Jun 2003 2 Posts Need help with math problem re: searching for all primes. About 10 years ago I created a mathematical algorythm that computes all the primes. I tested it against the first 2500 primes and it found them all (plus 2 or 3 non-primes). My program is slow to compute primes but I think that it could be sped up. I will do my best to describe it here (for those who wish to know more or have me explain something please email me at daxm@operamail.com). Okay here goes: To test if p is prime we run this program. (First setup some initial varialbles) d=p-1 (easier than computing p -1 all the time) i=1 (a counter) s=2 (This is our starting point) if(s<>1) s=(s*2)mod(d) i=i+1 endif When this is done then: if(d/i) is a whole number then p is prime. If there was only a quicker way to get to the d/i stage then we could zoom through all the primes. The problem is that i is a counter of how many times we goe through the loop. Any suggestions? Comments?
2003-06-09, 07:44   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Re: Need help with math problem re: searching for all primes

Quote:
 Originally Posted by daxm To test if p is prime we run this program. (First setup some initial varialbles) d=p-1 (easier than computing p -1 all the time) i=1 (a counter) s=2 (This is our starting point) if(s<>1) s=(s*2)mod(d) i=i+1 endif When this is done then: if(d/i) is a whole number then p is prime.
Let p = 9.
Then d = 9-1 = 8.

i = 1
s = 2

if(s&lt;>1) is true, so we continue

s = (s*2)mod(d) = 2 * 2 mod 8 = 4
i= 1+1 = 2

After the endif, we have i = 2, s = 4, d = 8

d/i = 4 = a whole number, so p = 9 is ... ??prime??

Is your if/endif section supposed to be some sort of loop? E.g., a while/endwhile?

 2003-06-11, 18:37 #3 flava     Feb 2003 11810 Posts I think he ment a while not a if, and this might be a variant of Fermat's little theorem a^(p-1) = 1 mod p. It finds pseudoprimes.
2003-06-13, 19:40   #4
daxm

Jun 2003

2 Posts
Re: Need help with math problem re: searching for all primes

Quote:
Quote:
 Originally Posted by daxm To test if p is prime we run this program. (First setup some initial varialbles) d=p-1 (easier than computing p -1 all the time) i=1 (a counter) s=2 (This is our starting point) if(s<>1) s=(s*2)mod(d) i=i+1 endif When this is done then: if(d/i) is a whole number then p is prime.
Let p = 9.
Then d = 9-1 = 8.

i = 1
s = 2

if(s&lt;>1) is true, so we continue

s = (s*2)mod(d) = 2 * 2 mod 8 = 4
i= 1+1 = 2

After the endif, we have i = 2, s = 4, d = 8

d/i = 4 = a whole number, so p = 9 is ... ??prime??

Is your if/endif section supposed to be some sort of loop? E.g., a while/endwhile?

Oops, I did mean WHILE. It is a looping equation until s==1.

 2003-06-13, 22:48 #5 S80780   Jan 2003 far from M40 53 Posts How would you handle candidates of the form p=2^n + 1? Except for n = 0 or some power of 2, they are all definitely composite. If n is a power of 2, p might or might not be prime. But your program would be unable to determine primality of any such number, as it would wind up in an infinite loop for d = 2^n. So from the (n - 1)th iteration on, all s - values are 0 <> 1. Benjamin
 2003-07-20, 19:32 #6 Annunaki   Jul 2003 378 Posts I just probably dont like to think right now and look through your algorith.. but at some point got interested.. could you describe on what idea is based this algorithm.. does it has some at least half proof why p after alhorithm is done could or could not be prime? i think it wouldnt be so efective for writing all primes in sequence as checking primarity for diferent numbers..

 Similar Threads Thread Thread Starter Forum Replies Last Post crack11 Homework Help 55 2020-08-13 11:18 joblack Lounge 20 2009-01-05 15:18 flosculus Information & Answers 6 2008-11-10 18:59 davieddy Math 7 2007-08-21 04:51 Erasmus Factoring 3 2004-05-14 09:26

All times are UTC. The time now is 15:40.

Fri Jan 15 15:40:54 UTC 2021 up 43 days, 11:52, 0 users, load averages: 1.79, 1.78, 1.76