p7-prime-number-10001.py

import math 
def get_prime(n):
    """
    Function to get the largest prime number dividing a certain number
    """
    # To factor out all the powers of 2
    while n % 2 == 0 and n != 2 : n = n/2
    
    # Starting out with 3
    i = 3
    
    # Checking till the square root of n
    while i < n and n / i > 0 :
        # Checking for divisibility with the ith number and reducing
        # n to reflect the divisibility
        while n % i == 0 and n != i:
            n = n / i
        # Increase i by 2, because the prime numbers are odd except for 2
        i = i + 2
    return n

def get_optimized_prime(n):
    if n < 4:
        return n
    while n % 2 == 0 and n != 2 : n = n/2
    if n < 9:
        return n
    while n % 3 == 0 and n != 3 : n = n/3
    # Starting out with 3
    i = 5
    
    # Checking till the square root of n
    while i <= math.floor(math.sqrt(n)) :
        # Checking for divisibility with the ith number and reducing
        # n to reflect the divisibility
        while n % i == 0 and n != i:
            n = n / i
        # Increase i by 2, because the prime numbers are odd except for 2
        i = i + 2
    return n

def traditional():
    s = set()
    i = 3
    s.add(2)
    while len(s) < 10001:
        s.add(get_optimized_prime(i))
        i = i + 2
    #print s
    ans = max(s)     
    return ans

print "Answer by traditional method:", traditional()