어떤 수가 소수인지 판별하기

오일러 프로젝트의 문제들 가운데에는 소수와 관련된 것들이 많다.

그래서 문제를 계속 풀기 전에 어떤 수가 소수인지 판별하는 코드를 작성하고 넘어가고자 한다.

소수는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 1보다 큰 자연수로 정의된다.

이 정의를 이용하여 어떠한 수가 소수인지 판별하기 위한 룰을 몇가지 생각해 볼 수 있다.

1. 2보다 작은 정수와 2를 제외한 짝수는 소수가 아니다. 

ex) 16: 2로 나누어 떨어지므로 소수가 아니다.

2. 그 수의 제곱근보다 작거나 같은 소수로 나누어 떨어지면 소수가 아니다. 

ex) 26: 2, 3, 5로만 나누어 떨어지는지 확인하면 된다.. 만약 4로 나누어 떨어진다면 2로도 나누어 떨어질 것이기 때문이다.

문제는 2번 룰에서, 소수를 찾기 위해서 소수를 찾아야 한다는 점이다.

이를 위하여 소수를 찾는 함수와 소수인지 판별하는 함수가 서로 재귀적으로 물리도록 하였다.

# -*- coding: utf-8 -*-

import numpy as np

class Prime:

	def __init__( self ):
	
		self.prime = [2,3]
		
	def is_prime( self, n ):
		
		if n < 2 : return False 
		
		# 기존의 소수 리스트에서 먼저 찾아본다.
		if n <= self.prime[-1] and n in self.prime: return True 
		
		# 그 수의 제곱근보다 작거나 같은 소수로 나누어 떨어지면 소수가 아니다.
		lim = np.floor( np.sqrt( n ) )
		
		if self.prime[-1] < lim: self.__find_prime__( lim )
			
		for p in self.prime:
		
			if lim < p: break
			if n % p == 0: return False
			
		return True
		
	def __find_prime__( self, n ):
		
		# 2를 제외한 소수는 홀수이다.
		prime_candidate = self.prime[-1] + 2
		
		while prime_candidate <= n:
		
			if self.is_prime( prime_candidate ):
			
				self.prime.append( prime_candidate )
			
			prime_candidate += 2
		
		return None

p = Prime()
print p.is_prime( 137 )