Check to see if a value is a prime number, introducing an isprime method.
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.Numbers
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.
Isprime method. We begin with the isprime method. It receives a candidate integer. It returns True or False based on whether it can detect a factor—whether the number is prime.
First part: The isprime method uses an if-statement, with a modulo division, to weed out even numbers. It special-cases 2 (a prime).
For, range: This part loops, starting at 3, through all possible factors. It increments by 2, skipping evens.
Square: In the for-loop, we eliminate a possible factor "i" if its square is more than the candidate number. This speeds things up.
Python program that checks for prime numbers
# No primes are even except 2.
# ... Use modulo division to test for even numbers.
if (candidate % 2) == 0:
if candidate == 2:
# 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:
# See if the number is evenly divisible.
if (candidate % i) == 0:
# 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):
# Test for primes in another range.
for test in range(10000, 10100):
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.For
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.MemoizeDictionary
Tip: Memoization is a good optimization to apply to a method like isprime above.
Also: Another option is to generate a list or dictionary of known primes and reuse it.
A brief history of primes. This prime-detecting method is a numerically intense one. With a JIT compiler, or a numeric optimization library for Python, performance improves.