ben_primes.py

import time


def ben_primes(limit, with_nones=False, bools=False):
    """
    Find prime numbers from 2 to the specified limit, return a list.

    Keyword arguments:
    with_nones -- if True, will return a list like [2, 3, None, 5, None, 7, None, None, None, 11]; Nones are otherwise omitted
    bools -- if True, ignores with_nones and returns a list like [True, True, False, True, False, True] where a number n's prime status can be found at list[n+2]
    """
    num_list = [True] * (limit - 1)

    for value in range(2, limit // 2 + 1):

        a = 2
        while value * a <= limit:
            num_list[value * a - 2] = False
            a += 1

    if bools:
        return num_list
    else:
        numerical_list = [val if num_list[val - 2] else None for val in range(2, limit + 1)]
        return numerical_list if with_nones else [num for num in numerical_list if num is not None]


def is_prime(x):
    import math

    for factor in range(2, math.floor(x ** 0.5) + 1):
        if x % factor == 0:
            return False
    if x <= 1:
        return False
    return True


if __name__ == '__main__':
    test_limit = 1000000

    time0 = time.time()
    ben_1M = ben_primes(test_limit)
    time1 = time.time()

    time2 = time.time()
    my_1M = [num for num in range(2, test_limit + 1) if is_prime(num)]
    time3 = time.time()

    time4 = time.time()
    ben_bool = ben_primes(test_limit, bools=True)
    time5 = time.time()

    print('Ben method took %s' % str(time1 - time0))
    # print(ben_1M)
    print('My method took %s' % str(time3 - time2))
    # print(my_1M)
    print('Ben bools only took %s' % str(time5 - time4))

ben_primes is now faster than is_prime.

With a limit of 1,000:

With a limit of 100,000:

With a limit of 10,000,000:

The speedup is particularly noticeable in the above example.

The booleans-only method is marginally faster when it returns booleans than when it converts the booleans into a normal list of integers (limit of 1,000,000):

And for comparison, with a limit of 100,000:

Somehow the new method is slower than the old. Oh well, I probably screwed something up.