Primes

A prime number is not divisible by any number other than 1 and itself. Primes have many applications in computer software, from cryptography to hash tables.

To test for primes, a method can analyze a number for divisors. Some optimizations though are important: this speeds up prime detection. And caches are also helpful.

Is_prime method

We begin with the is_prime method. It receives a candidate integer. It returns True or False based on whether it can detect a factor—whether the number is prime.

def is_prime(candidate):
    # No primes are even except 2.
    # ... Use modulo division to test for even numbers.
    if (candidate % 2) == 0:
        if candidate == 2:
            return True
        else:
            return False

    # Loop over numbers incrementing by 2 to the number.
    for i in range(3, candidate, 2):
        # No prime can be more than the square root.
        if (i * i) > candidate:
            break;
        # See if the number is evenly divisible.
        if (candidate % i) == 0:
            return False

    # The candidate is a prime unless it is 1.
    return candidate != 1

# Test for primes in first 100 numbers.
for test in range(0, 100):
    if is_prime(test):
        print(test)

# Test for primes in another range.
for test in range(10000, 10100):
    if is_prime(test):
        print(test)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
10007
10009
10037
10039
10061
10067
10069
10079
10091
10093
10099

With modulo division, we test if a number is evenly divisible by another number. This is efficient. But other parts, like the for-loop, will be slow in extensive use.

Memoization

This is an approach to optimize repeated calculations. In memoization (which is not misspelled, referring to "memo") a method's result is stored in a dictionary.

Summary

This prime-detecting method is a numerically intense one. With a JIT compiler, or a numeric optimization library for Python, performance improves.