#
All Primes

#======================================================================= # Author: Isai Damier # Title: All Primes # Project: geekviewpoint # Package: algorithms # # Statement: # Given a number n, return all prime numbers less than or equal to n. # # Sample Input: 35 # Sample Output: [2,3,5,7,11,13,17,19,23,29,31] # # Time Complexity of Solution: # Best = Average = Worst = O(Time) = O(n log log n), # where n is the max 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 # # Approach: # 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^2 = x); then if x is not # divisible by any number between 2 and y inclusive, then x is prime. # # This is an "innocent until proven guilty" algorithm that capitalizes # on the above arithmetic facts to find all primes between 2 and n. In # the innocent until proven guilty paradigm, all candidates start out # as winners. Then through a rigorous process, the algorithm winnows # the faulty candidates until the elite is left. Known as the sieve of # Eratosthenes, there are a number of ways to implement the set of # arithmetic rules above into an algorithm. The following is easy to # understand. # # 0] Declare a bit vector and initialize all the keys from 0 to # x with the value 'true' -- making them all primes. # 1] For keys 0 and 1, set the values to false # 2] For each number n between 2 and x, set all multiples of n to false. # 3] Group together all keys whose values are still true and # return that group. # # There are a number of ways to improve the time complexity of this # program, such as considering only odd numbers as opposed to all # numbers between 2 and n. #======================================================================= from math import sqrt def allPrimes( num ): if 2 > num: return None primes = [True] * ( num + 1 ) primes[0] = primes[1] = False _sqrt = int( sqrt( num ) + 1 ) for i in range( 2, _sqrt ): if primes[i]: k = 2 while k * i <= num: if primes[k * i]: primes[k * i] = False k += 1 result = [] for i in range( 2, num + 1 ): if primes[i]: result.append( i ) return result

import unittest from algorithms import numbers as algorithm class Test( unittest.TestCase ): def testAllPrimes( self ): expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] self.assertEquals( expected, algorithm.allPrimes( 30 ) ) expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] self.assertEquals( expected, algorithm.allPrimes( 31 ) ) expected = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] self.assertEquals( expected, algorithm.allPrimes( 40 ) )