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.
Note The is_prime method uses an if-statement, with a modulo division, to weed out even numbers. It special-cases 2 (a prime).
Next The for loops, starting at 3, through all possible factors. It increments by 2, skipping evens.
Info In the for-loop, we eliminate a possible factor "i" if its square is more than the candidate number. This speeds things up.
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.
Tip Memoization is a good optimization to apply to a method like is_prime above.
Also Another option is to generate a list or dictionary of known primes and reuse it.
Summary. This prime-detecting method is a numerically intense one. With a JIT compiler, or a numeric optimization library for Python, performance improves.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.