All Primes
by Isai Damier

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