가장 큰 소인수 구하기, 소수의 합 구하기

from bisect import bisect_left
import math
 
def intSqrt(f):
    x = math.sqrt(f)
    return math.floor(x)
 
def isPrime(num, S):
    if num < 10:
        return num in [2, 3, 5, 7]
    y = intSqrt(num)
    pos = bisect_left(S, y)
    for i in range(0, pos+1):
        if num % S[i] == 0:
            return False
    return True
 
def PrimeSet(num):
    P = [2]
    for i in range(3, num+1, 2):
        if isPrime(i, P):
            P.append(i)
    return P
 
x = 2000000
S = PrimeSet(x)
print(sum(S))

from bisect import bisect_left
import math
 
def intSqrt(f):
    x = math.sqrt(f)
    return int(math.floor(x))
 
def isPrime(num, S):
    if num < 10:
        return num in [2, 3, 5, 7]
    y = intSqrt(num)
    pos = bisect_left(S, y)
    for i in range(0, pos+1):
        if num % S[i] == 0:
            return False
    return True
 
def PrimeSet(num):
    P = [2]
    for i in range(3, num+1, 2):
        if isPrime(i, P):
            P.append(i)
    return P
 
 
x = 600851475143
# sorted, list of prime numbers <= sqrt(x)
L = PrimeSet(intSqrt(x))
 
# tab[x] is the maximum prime number that is equal to or less than x
tab = dict()
for p in L:
    tab[p] = p
 
def getAB(n):
    """
    for a prime number n, return 1, n
    for others, return a, b where n = a * b, a <= b,
    and a is the smallest factor of n except 1
    """
    y = intSqrt(n)
    pos = bisect_left(L, y)
    # L[pos] >= intSqrt(n) if pos < len(L)
    # or, all e in L < intSqrt(n)
    to = pos
    if pos < len(L) and L[pos] == y:
        to = to + 1
    for i in range(0, to):
        if n % L[i] == 0:
            return L[i], n//L[i]
    return 1, n
 
def max_prime(n):
    """
    if n is already calculated (e.g. small prime number) or
         is a prime number (pretty much greater than sqrt(x)),
       tab[n] = n, and return it
 
    Now, n = a * b, a <= b < n. a is the smallest factor of n but 1.
    b is the greatest factor of n but n itself
    """
    if n in tab or isPrime(n, L):
        if not n in tab:
            tab[n] = n
        return tab[n]
 
    a, b = getAB(n)
    if isPrime(b, L):
        tab[n] = b
        tab[b] = b
        return b
 
    tab[n] = max(max_prime(a), max_prime(b))
    return tab[n]
 
print(str(x) + " : " + str(max_prime(x)))

from math import sqrt
 
def intSqrt(f):
    return int(sqrt(f))
 
def get_prime():
    primes = [2, 3]
    for p in primes:
        yield p
 
    def is_prime(n):
        sqrt_n = intSqrt(n)
        for p in primes:
            if p > sqrt_n:
                return True
            if n % p == 0:
                return False
        return True
 
    i = 6
    while True:
        for j in (-1, 1):
            if is_prime(i+j):
                yield i+j
                primes.append(i+j)
        i += 6
 
def prime_factors(n):
    sqrt_n = intSqrt(n)
 
    for p in get_prime():
        if p > sqrt_n:
            yield n
            break
        if n % p == 0:
            yield p
            while n % p == 0:
                n //= p
            sqrt_n = intSqrt(n)
 
def prime_sum(n):
    sum = 0
    for p in get_prime():
        if p > n:
            break
        sum += p
    return sum
 
def P3():
    return max(prime_factors(600851475143))
 
def P10():
    return prime_sum(2000000)