I made a primality tester with trial division. I'm trying to make it as fast as possible and have reached the point now where I'm out of ideas.
I use the generator approach and not lists because I found out that it's awfully slow to generate and checklists for big ranges.
Does someone have ideas on how to improve the
seeker() functions? I left some comments in the code to explain why I did it like this.
#!/usr/bin/env python # -*- coding: utf-8 -*- ''' Made for Python 2.7.x See __main__ block at the end of this script to change the range to be searched. ''' from math import sqrt as math_sqrt def is_prime_td(num): ''' Test if a number is a prime with Trial Division. num: The number to be tested. Returns True if num is a prime and False if not. ''' # No prime if smaller than 2 if num < 2: return False # 2 is the only even prime if num == 2: return True # No prime if if num can be divided by 2 w/o a remainder except 2 itself if num % 2 == 0: return False # Check if num is divisible by any odd number (except 1) up two # ceil'ed square root of num. I didn't want to call math.ceil() # so i added just "+ 1" i = 3 while i <= int(math_sqrt(num) + 1): # No prime if if num can be divided by i w/o a remainder if num % i == 0: return False # Go test with the next odd divisor i += 2 # It's a prime if not proven false until here return True def seeker(num_start, num_end): ''' Search for primes from and including num_start to num_end. Uses 'is_prime_td()'. ''' # The smallest prime number is two. So, always skip if num's < 2. # We could add this check also to the loop below where we Increment # accordingly, but this would just add a useless extra check each # iteration. if num_start >= 2: num = num_start else: num = 2 try: while num <= num_end: if is_prime_td(num): yield num # Since there are no even primes except 2, we only want to # test odd numbers in the loop. Increment accordingly so we never # test even numbers and thus saving some time. if num % 2 == 0: num += 1 else: num += 2 except KeyboardInterrupt: pass if __name__ == '__main__': # Define the range to be searched here. num_start = 0 num_end = 100 # Print only positive findings. for num in seeker(num_start, num_end): print num