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 is_prime_td()
and 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