Python Notes

FirstClassObjects

In the terminology of programming languages, first-class Objects are instances of a type
that can be assigned to an identifier, passed as a parameter, or returned by a function
In Python classes and functions are also treated as first-class Objects.

For Example
scream = print 
# assign name 'scream' alias name to print

Modules are also first-class objects in Python


from math import sqrt
import timeit
import time

n10000 = 104729
nnrime = 664579
n1000 = 7919


def primeSieve_01(upton):
  '''
  Returns a list of prime numbers calculated using the Sieve of Eratosthenes algrotithm
  '''
  sieve = [True] * upton
  sieve[0] = False #Zero and one are not prime number
  sieve[1] = False
  # checking the divisibilty till Square root of it
  limit = int(sqrt(upton)) + 1
  for index in range(2,limit):
    if sieve[index]:
      pointer = index * index
      for inner_index in range(pointer,upton,index):#for inner loop increase the step size by outer index 
        # print (sieve[inner_index], inner_index)
        sieve[inner_index] = False
        # print (sieve[inner_index])

  return sieve


def isPrime_01(number):
  upton = number + 1
  # start = time.clock()
  checked = primeSieve_01(upton)
  # print (time.clock() - start)
  if checked[number]:
    return True
  return False



if __name__ == '__main__':
  def isPrime_naive_time():
    isPrime_naive0000t = timeit.Timer('isPrime_01(n10000)','from __main__ import isPrime_01, n10000')
    print ("Time to check 1000th prime", isPrime_01(n10000),isPrime_naive0000t.repeat(3,10), "sec" )
    isPrime_naive00000t = timeit.Timer('isPrime_01(nnrime)','from __main__ import isPrime_01, nnrime')
    print ("Time to check 10000th prime", isPrime_01(nnrime),isPrime_naive00000t.repeat(3,10), "sec" )

# isPrime_naive_time()
# Time to check 1000th prime True [0.15272743133954594, 0.15201311630198286, 0.14999640789851804] sec
# Time to check 10000th prime True [1.0718004638942484, 1.0670989162116673, 1.060605423046923] sec
# [Finished in 4.0s]

'''
Improving the Sieve 
'''

def prime_sieve_02(upton):
  '''
  This function gets a further improvement by 
  removing even number from the sieve since they are never prime except
  for 2.
  This yields up the speed by two things first we have to tick only
  few members and seconds only half of the space is required
  '''
  limit = int(sqrt(upton)) + 1
  sieve = [True] * (upton // 2)

  for index in range(0,limit):
    if sieve[index]:
      index_square = (2 * index * (index + 3) ) + 3
      increment = 2 * index + 3
      for inner_index in range(index_square,limit,increment): # increment should be till limit only as we are checking for half only
        sieve[inner_index] = False

  return sieve


def isPrime_02(number):
  if number <= 1:
    return False
  if not number & 1:
    return number == 2
  upton = number + 1
  # start = time.clock()
  checked = prime_sieve_02(upton)
  index = (number - 3) >> 1
  # print (time.clock() - start)
  if checked[index]:
    return True
  return False

# print (isPrime_02(n1000))
if __name__ == '__main__':
  def isPrime_naive_time_01():
    isPrime_naive0000t = timeit.Timer('isPrime_02(n10000)','from __main__ import isPrime_02, n10000')
    print ("Time to check 1000th prime", isPrime_02(n10000),isPrime_naive0000t.repeat(3,10), "sec" )
    isPrime_naive00000t = timeit.Timer('isPrime_02(nnrime)','from __main__ import isPrime_02, nnrime')
    print ("Time to check 10000th prime", isPrime_02(nnrime),isPrime_naive00000t.repeat(3,10), "sec" )

# isPrime_naive_time_01()
# Time to check 1000th prime True [0.0038928116917771667, 0.003753232891333799, 0.003942587955170573] sec
# Time to check 10000th prime True [0.027007471571082554, 0.026727287655486674, 0.025813867564349932] sec
# [Finished in 0.3s]

'''
Improving the sieve further with strength reduction
'''