Home
Python
Prime Number Method
This page was last reviewed on Dec 15, 2021.
Dot Net Perls
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.
def
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.
Note The isprime 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 isprime(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 isprime(test): print(test) # Test for primes in another range. for test in range(10000, 10100): if isprime(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.
while
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.
Memoize
Dictionary
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.
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 tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Dec 15, 2021 (edit link).
Home
Changes
© 2007-2024 Sam Allen.