Simple prime number search with trial division

Question

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

Answer 1

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 < 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 <= 2 <= 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

Answer 2

Updated Code 1

Initial question/version

---

Okay i've tried my best to improve the code depending on the tips from Peilonrayz's answer.

Please let me know if it makes sense how I changed the things.

---

Here's what I've changed, what not and some explanations from me. Quoting Peilonrayz's tips.

(The code is below)

changed: Remove unneeded comment. 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.

I never thought this way about my comments. I totally see what you mean. Have to let that bad habit go and learn more about "best practices in code documentation".

changed: Change the while to not square root num each iteration.

changed: Change the code to use the less accurate ** operator, rather than math.sqrt.

changed: Change seeker to yeild 2 if it's within the domain.

changed: Move the keyboard interrupt code out of the function, into the main. As functions are meant to do one thing, not two.

not changed: Change seeker to use a for loop, to simplify the code.

Still using a while loop. I tried it with range() and xrange(), but both fail when the range is very big. Also itertools.count(start, step) would be an option but then I can't adjust the step on the fly in the seeker() function, and it's an extra function call.

This is what I mean it fails with big ranges:

# fails: OverflowError: range() result has too many items
for i in range(0, 10000000000000000000):
    pass

# fails: OverflowError: Python int too large to convert to C long
for i in xrange(0, 10000000000000000000):
    pass

not changed: Instead of doing this you should instead use a sieve, where you filter the output.

I can't figure out how to do this without lists so it doesn't hit memory limits when the range to be searched is very big.

---

My Updated Script Code

#!/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_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.
    '''
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False

    last_trial_num = int(num ** 0.5) + 1
    i = 3
    while i <= last_trial_num:
        if num % i == 0:
            return False
        i += 2

    return True


def seeker(num_start, num_end):
    '''
    Search for primes from and including num_start to num_end.
    Uses 'is_prime_td()'.

    Yields prime numbers.
    '''
    if num_start <= 2:
        yield 2
        num_start = 3

    num = num_start
    while num <= num_end:
        if is_prime_td(num):
            yield num

        if num % 2 == 0:
            num += 1
        else:
            num += 2


if __name__ == '__main__':
    num_start = 0
    num_end   = 100

    try:
        for num in seeker(num_start, num_end):
            print num
    except KeyboardInterrupt:
        pass