Python Prime Number Method

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 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) Output 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.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.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.

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Python Prime Number Method

Related Links:

.Net

Java

Related Links