Is Prime
by Isai Damier

#=======================================================================
# Author: Isai Damier
# Title: isPrime
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#  Indicate whether the given number is prime.
#
# Sample Input: 31
# Sample Output: true
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(Time) = O(n log log n),
#   where n is the number to test. You can verify this as
#   O(Time) = n/p1+n/p2+... = n*sum(1/p) for all prime p < n^0.5
#
# Technical Details:  Arithmetic review:
#   0) 0 and 1 are not prime numbers.
#   1) The first prime number is 2.
#   2) A number is prime if it is only divisible by itself and by 1
#   3) If y is the square root of x (i.e. y = x^0.5); then if x is not
#      divisible by any number between 2 and y, inclusive; then x is prime.
#
# Alternate Algorithm:
#   if 2 > num: return False
#   if 2 == num: return True
#   if 0 == num %2: return False
#   SQRT = long( math.sqrt(num))
#   for i in range(3,SQRT+1,2)
#     if 0 ==  num % i:
#       return false
#   return true
#======================================================================= 
 from math import sqrt
def isPrime( num ):
  if 2 > num:
    return False

  primes = [True] * ( num + 1 )
  primes[0] = primes[1] = False
  _sqrt = int( sqrt( num ) )
  i = 2
  while i <= _sqrt and primes[num]:
    if primes[i]:
      k = 2
      while k * i <= num:
        if primes[k * i]:
          primes[k * i] = False
        k += 1
    i += 1
  return primes[num]
import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testIsPrime( self ):

      self.assertFalse( algorithm.isPrime( 0 ) )
      self.assertFalse( algorithm.isPrime( 1 ) )
      self.assertTrue( algorithm.isPrime( 2 ) )

      self.assertTrue( algorithm.isPrime( 37 ) )
      self.assertFalse( algorithm.isPrime( 58 ) )
      self.assertTrue( algorithm.isPrime( 71 ) )

      self.assertTrue( algorithm.isPrime( 89 ) )
      self.assertFalse( algorithm.isPrime( 98 ) )
      self.assertTrue( algorithm.isPrime( 157 ) )

      self.assertFalse( algorithm.isPrime( 177 ) )
      self.assertTrue( algorithm.isPrime( 199 ) )
      self.assertTrue( algorithm.isPrime( 281 ) )

      self.assertFalse( algorithm.isPrime( 417 ) )
      self.assertTrue( algorithm.isPrime( 479 ) )
      self.assertTrue( algorithm.isPrime( 523 ) )

      self.assertFalse( algorithm.isPrime( 1089 ) )
      self.assertTrue( algorithm.isPrime( 1123 ) )
      self.assertTrue( algorithm.isPrime( 2029 ) )

      self.assertFalse( algorithm.isPrime( 3447 ) )
      self.assertTrue( algorithm.isPrime( 3539 ) )
      self.assertTrue( algorithm.isPrime( 3571 ) )

      self.assertFalse( algorithm.isPrime( 7917 ) )
      self.assertTrue( algorithm.isPrime( 27751 ) )
      self.assertTrue( algorithm.isPrime( 93563 ) )