 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 28 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

1C1416 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 3110 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..  Thread Tools Show Printable Version Email this Page 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 02:30.

Wed Nov 25 02:30:38 UTC 2020 up 75 days, 23:41, 4 users, load averages: 1.47, 1.52, 1.44