Simple prime number search with trial division 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 &lt; 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 &lt;= 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 &lt; 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 &gt;= 2:
        num = num_start
    else:
        num = 2

    try:
        while num &lt;= 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
Instead of doing this you should instead use a sieve, where you filter the output. It would make the code much simpler, and would make it much faster.



Your comments are useless at best. If you know two languages it'd not make sense to say the same thing in both. Which is what you are doing here. Instead what you want to use comments for, is for high-level overviews of your code.

Say you create a primality test which is heavily optimized, you would want to put a comment on the hard to read parts. Such as your sqrt part.

To improve the actual code, I'd:


Remove unneeded comment.
Change the while to not square root num each iteration.
Change the code to use the less accurate ** operator, rather than math.sqrt. You're using int and adding by 1 anyway, so it won't make a difference.
Change seeker to yeild 2 if it's within the domain.
Change seeker to use a for loop, to simplify the code. As with the above you don't need to increment by one ever.
Move the keyboard interrupt code out of the function, into the main. As functions are meant to do one thing, not two.




#!/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.
"""

def is_prime(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.
    """

    if num &lt; 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False

    # Check if number is divisible by any odd number,
    # from one to the square root of the number.
    # as one of a or b will be in this range,
    # for all a and b that are `a * b = num`.
    for i in range(3, int(num ** 0.5) + 2, 2):
        if num % i == 0:
            return False
    return True


def seeker(num_start, num_end):
    """
    Search for primes from and including num_start to num_end. 
    Uses 'is_prime_td()'.
    """
    # Force `num_start` to be odd with xor, ^. And go up in twos.
    if num_start &lt;= 2 &lt;= num_end:
        yield 2
    for i in range(max(3, num_start ^ 1), num_end + 1, 2):
        if is_prime_td(num):
            yield num


if __name__ == '__main__':
    num_start = 0
    num_end   = 100
    try:
        for num in seeker(num_start, num_end):
            print num
    except KeyboardInterupt:
        pass