[Project Euler]3. Largest prime factor

[문제]
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 

[풀이]
2021.05.24
def find_primeNumber(n):
    primeNumbers = [2,3]
    if n<=7:
        pass
    else:
        for i in range(4, n+1):
            for pn in primeNumbers:
                if i%pn==0:
                    break
                if pn==primeNumbers[-1]:
                    primeNumbers.append(i)
    return primeNumbers


def find_primeFactor(n):
    primeFactors = []
    primeNumbers = find_primeNumber(n)

    number = n

    while number not in primeNumbers:
        for pn in primeNumbers:
            if number%pn==0:
                number = int(number/pn)
                primeFactors.append(pn)
                break
    primeFactors.append(number)

    return primeFactors

+) 2021.05.25 추가
def find_primeFactor(n):
    primeFactors = []
    number = n

    while number !=1:
        for i in range(2,n+1):
            if number%i==0:
                number = int(number/i)
                primeFactors.append(i)
                break

    return primeFactors


a = find_primeFactor(600851475143)
print(max(a))

 

'''
2021.05.24
일단 n이하의 모든 소수를 구해서 그 소수로 나눠서 나눠떨어지면 primeFactors에 넣는 방식으로 구현했다.
(n이하의 소수를 구하는 함수 하나, 소인수를 구하는 함수하나)

일단 풀긴 풀었는데 문제의 답을 연산하는데 시간이 너무 오래 걸린다...
너무 비효율적인 모양이다..
다른 방법을 찾아보기로 해야겠다.. 쩝

+) 2021.05.25
풀었다! 이제 답도 나온다
굳이.. 소수를 구할필요가 없었다.
시간이 오래 걸리던건 소수를 구하느라 오래 걸렸던 듯 하다.

2부터 1씩 더해가면서 나눠지면 나누고 나눠지지 않으면
다음으로 넘어가면 굳이 소수를 구하지 않아도 소수로 나눠진다!

'''