February 7th, 2005, 06:11 PM

Speeding up prime search
I am working on a prime number finder. I want it to do it as fast as possible so i was wondering if i could have other maybe look at my code and look for optimzations i could put in
Code:
#!/usr/local/bin/python2.3
def testPrime(addNum):
#ok lets set it up so it figures if it is prime or not
num = addNum
comparNum = num
testNum = 3
while testNum < comparNum:
if not num % testNum:
return 0;
comparNum = num / testNum + 1
testNum = testNum + 2
print addNum
return addNum
primes = []
currentNum = 3
while (1):
#lets start off with putting the current adding num up
checkPrime = testPrime(currentNum)
if checkPrime:
primes.append(currentNum)
currentNum += 2
This is a simplified v. of my prime searcher. Mine saves to text files, but i don't think my preformance lose is there. I know how this code is it would overload your memory quickly because of the list of primes. But with mine that is dumped to a text file and started fresh ever once in a while so that isn't a problem. I am more or less looking at what checks if it is prime if there is a way to speed that up?
thanks for anyones help
February 7th, 2005, 09:24 PM

What are you trying to do? How large of primes are you looking for? Realize that primality testing is a key feature of cryptography, and lots of Phd's have been working on how to do this sort of thing fast. The fastest deterministic methods are somewhere around O(n^12), which is WAY too slow for large primes. The general strategy for primality testing is to sieve (which means to just check if the first several primes are factors), then do a randomized algorithm like MillerRabin (or RabinMiller if you prefer). The MillerRabin algorithm is will never tell you for 100% for sure if a number is prime, but you can be sure to 99.999999999999% quite quickly.
This might be more than you wanted to know, and if it is, sorry. If you tell me more about how large of primes you are going to be looking for, or what the application is I can help you more. Also, you can look at the resources on prime.py and primes.py, it looks like others in the python world have put forth a lot of effort already into cryptographic modules.
Hope this helps
EDIT: More directly answering your question, though, I could offer the following advice right away... in your function you check all odd numbers to see if they are divisors. It would speed things up a bunch if you only checked the primes you have found so far. Let me know if this doesn't make sense.
Comments on this post
February 7th, 2005, 10:51 PM

I am actually looking for a very very very large prime number. Actually for not really any reason lol just because i want to see if i can do it. I am wanting to set it up so it distributes it across multiple computers. Infact i almost have the system for that completed.
I first went through a lot of numbers and got abou 1500 numbers had no factors of the first 1100,000 primes. Now i want to cut that list down. But i want to prove behond all reasonible dubt that this number is prime. I know it sounds insain but why not? lol
That is why that cod ethere just checks odds because i wasn't sure if it should check more
If you would like to look at the more complete prime finder i have you can it is opensource just im me or email me and i will send it.
There is still a lot of work but i just want a better way. I know there are others out there, I just think i need to know about them more
thanks for all your infomation