20030608, 22:58  #1 
Jun 2003
2_{8} 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 nonprimes). 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=p1 (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? 
20030609, 07:44  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1C14_{16} Posts 
Re: Need help with math problem re: searching for all primes
Quote:
Then d = 91 = 8. i = 1 s = 2 if(s<>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? 

20030611, 18:37  #3 
Feb 2003
118_{10} Posts 
I think he ment a while not a if, and this might be a variant of Fermat's little theorem a^(p1) = 1 mod p. It finds pseudoprimes.

20030613, 19:40  #4  
Jun 2003
2 Posts 
Re: Need help with math problem re: searching for all primes
Quote:
Oops, I did mean WHILE. It is a looping equation until s==1. 

20030613, 22:48  #5 
Jan 2003
far from M40
5^{3} 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 
20030720, 19:32  #6 
Jul 2003
31_{10} Posts 
I just probably don`t 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 wouldn`t 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 
math gcd problem need help  crack11  Homework Help  55  20200813 11:18 
Searching for m. primes is like playing lottery  joblack  Lounge  20  20090105 15:18 
to be faster at searching mersenne primes  flosculus  Information & Answers  6  20081110 18:59 
searching for Mersenne primes  davieddy  Math  7  20070821 04:51 
A Proposal for searching Recurrence Series Primes  Erasmus  Factoring  3  20040514 09:26 