3. Largest prime factor

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

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

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

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

# -*- 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. 약수 중 소수 [본문으로]