Project Euler 3

Question: 

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

문제:

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

Solution:

from math import sqrt
 
primes = set([2])
value = 3
number = 600851475143
while value < sqrt(number):
    isPrime = True
    for k in primes:
        if value % k == 0:
            isPrime = False
            value += 2
    if isPrime:
        primes.add(value)
        if number % value == 0:
            print(value)
            number /= value
print(int(number))

square root를 쓰기위해서 모듈 math 에서 메소드 sqrt 를 import 해왔다.

가장 큰 소인수는 sqrt(number)보다 작은 점을 이용하여 while loop을 짜고,

for loop 에서 소수인지 확인, 아닐경우 2를 더해주고, 소수일 때 까지 반복. 2를 제외한 짝수는 소인수가 될 수 없기 때문.

소인수일 경우에는, 본 수를 나눈다.

from math import sqrt
from sympy import sieve
 
number = 600851475143
primes = list(sieve.primerange(1,sqrt(number)))
 
print([primes[x] for x in range(len(primes)) if number % primes[x] == 0][-1])

6857