mersenneforum.org Need help with math problem re: searching for all primes.
 User Name Remember Me? Password
 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
cheesehead

"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 2·59 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:
Originally Posted by cheesehead
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 12510 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 31 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

 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 10:40.

Sat Oct 31 10:40:12 UTC 2020 up 51 days, 7:51, 2 users, load averages: 2.01, 1.88, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.