# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

# Task 3: Largest prime factor

# This time we are dealing with a prime factorization problem and most of "naive" factorization algorithms are not very effective, so we cannot use bruteforce this time, so, at first, we'll try to improve it. 
#
# This is primitive realisation of a naive factorization algorithm, that has O(∑(Ni)) complexity:

# +
def is_prime(N):
    for i in range(2, N):
        if N % i == 0:
            return False
    return True
        

def greatest_prime(N):   
    max_prime = 1    
    for i in range(2, N):
        if N % i == 0 and is_prime(i):
            max_prime = i
    return max_prime    
        

print(greatest_prime(600851475143))        

# -

# Firstly, we need to decrease the upper bound of each cycle to sqrt(N), cause there are no natural divisors of a number, that exceed sqrt(N).
#
# And we get an algorithm with O(∑(sqrt(Ni))) complexity, that already able to compute required number quickly:

# +
import math


def is_prime(N):
    for i in range(2, int((math.sqrt(N)))+1):
        if N % i == 0:
            return False

    return True


def greatest_prime(N):
    max_prime = 1
    for i in range(2, int((math.sqrt(N)))+1):
        if N % i == 0 and is_prime(i):
            max_prime = i
    return max_prime


print(greatest_prime(600851475143))
# -

# But we'll try to implement an algorithm called "Eratosthenes sieve", that has O(n*log(log n)) complexity and can effictively help us find factorization of big integers.
#
# Here is one of the implementations:

# +
import math

def eratosthenes(n):
    sieve = list(range(n + 1))
    sieve[1] = 0
    for i in sieve:
        if i > 1:
            for j in range(i + i, len(sieve), i):
                sieve[j] = 0
    return sieve


outcome_primes = list(filter(lambda x: x != 0, eratosthenes(int(math.sqrt(600851475143))+1)))


for i in outcome_primes:
    if 600851475143 % i == 0:
        max_prime = i

print(max_prime)
# -



StarcoderdataJupyterScriptsDedupFiltered