3. Largest prime factor

문제는 이곳에서 확인할 수 있다. 

600851475143의 가장 큰 소인수^[각주:1]를 찾는 문제인데, 이를 해결하기 위해서는 어떤 수가 소수인지 먼저 파악해야 한다.

이를 위하여 소수 판별에 관한 내용을 따로 포스트하였다. 

600851475143를 소수로 계속 나누되 1을 만드는 소수를 찾으면 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

# -*- coding: utf-8 -*-   import numpy as np import utils as u # class Prime   p = u.Prime()   n = 600851475143   # n is not divisible by 2 prime_candidate = 3 find_prime = True   while True:           while not p.is_prime( prime_candidate ):                   prime_candidate += 2           while n % prime_candidate == 0:               n /= prime_candidate           if n == 1: break           prime_candidate += 2       print prime_candidate

답은 6857이다.

1. 약수 중 소수 [본문으로]