#=======================================================================
# 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 ) )
