Tutorial, Is a Prime Number

2015-02-03

Basic

In this tutorial, we try to check whether a number is a prime number and also learn list, set, and doctest module.

We can learn a module like, in python interactive input, as following(">" is the prompt indicator):

> import doctest
> help(doctest)

We will use simple doctest to check our code working as expected.

import doctest>

Prime Number

A number is prime can be verified by that all prime numbers which are less than that numbers can not divide it exactly. We can loose that all less prime numbers to all less numbers. We can also stop to check if have checked sufficient large numbers. It can be easily checked that any non prime number has a factor not greater than its square root.

To speed up the check and simplify the logical, we can build a list of small prime numbers, and check of every number in that list is not a factor first, after that, only odd factors are still need to check.

# kSmallPrimerNumbers is a list of all small prime numbers less than a specific
# value in order.
kSmallPrimeNumbers = [2, 3, 5, 7, 11, 13]

# The maximal small prime number.
kMaxSmallPrimeNumber = kSmallPrimeNumbers[-1]

kSmallPrimeNumberSet is a set of all small prime numbers less than a specific value. The numbers in this set should be the same as kSmallPrimeNumbers. This set is used to quickly check whether a small number is a prime number. We can check whether a small number \(n\) is a prime by n in kSmallPrimerNumbers. But if the list kSmallPrimerNumbers is large, this will loop over all elements of kSmallPrimerNumbers and compare every element with n. That is so called linear complexity, which is usually very slow for large list. The set in Python is a hash set, which store numbers in buckets, all numbers with the same hash will be stored in the same bucket. To find a number in a set, we calculate the hash of that number first, and only need to find in the bucket with the same hash. This is usually a constant complexity (in average).

kSmallPrimeNumberSet = set(kSmallPrimeNumbers)

def IsPrime(n):
  """Returns true if n is a prime number, otherwise returns false.

  >>> IsPrime(2)
  True

  >>> IsPrime(4)
  False

  >>> IsPrime(31)
  True
  """
  assert isinstance(n, int)
  assert n > 0
  if n in kSmallPrimeNumberSet:
    return True
  if n < kMaxSmallPrimeNumber:
    return False
  for p in kSmallPrimeNumbers:
    if n % p == 0:
      return False
  for d in range(kMaxSmallPrimeNumber, n, 2):
    if d * d > n:
      break
    if n % d == 0:
      return False
  return True

We can collect all code pieces to a file, like is_prime.py. The file can be used as other Python module. We can also embeded some check logical in the same file:

if __name__ == "__main__":
  # This called list comprehension. It can be read as a set expression in
  # mathematics.
  print("list comprehension primes:", [i for i in range(1, 100) if IsPrime(i)])
  # The general forms of list compression are:
  #
  # [value-expression for value in iterable],
  #
  # [value-expression for value in iterable if value-check]
  #
  # The above list comprehension can be rewritten as:
  result = []
  for i in range(1, 100):
    if IsPrime(i):
      result.append(i)
  print("list appended primes:", result)
  prime_squares = [i * i for i in range(1, 100) if IsPrime(i)]
  print("prime squares:", prime_squares)
  import doctest
  doctest.testmod()

Please note that if this file is used as a module, the last check part is protected by a false condition, and ignored.

Problems

Problem 1Learn Python set module.

Problem 2Use the defined IsPrime in a file is_file, use it to print all prime numbers less than 1000.