#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2004
    Posts
    461
    Rep Power
    24

    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
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2005
    Posts
    37
    Rep Power
    10
    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 Miller-Rabin (or Rabin-Miller if you prefer). The Miller-Rabin 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

    • SimonGreenhill agrees : +1 Informative
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2004
    Posts
    461
    Rep Power
    24
    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 1-100,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

IMN logo majestic logo threadwatch logo seochat tools logo