에라토스테네스의 체 - 소수 구하기

소수 : 약수가 1과 자기자신 뿐인 수

소수를 구하는 알고리즘을 짤 때, 가장 효율적인 방법으로 에라토스테네스의 체를 이용한다.

체에 거르듯이 숫자들을 걸러내는 방식이다. 

def solution(N):
	sieve = [True] * (N + 1) #1
    m = int(N ** 0.5) #2
    for i in range(2, m+1): #3
    	if sieve[i]: #4
        	for j in range(i+i, N+1, i): #5
            	sieve[j] = False 
  	result = [i for i in range(2, N+1) if sieve[i]] #6
    return result

1. sieve(체)라는 변수에 길이가 N+1인 True로 채워진 리스트 생성한다. 

   (길이가 N+1인 이유는 리스트의 인덱스는 0부터 시작하기 때문에 N까지 소수 판별하기 위함)

2. m 이라는 변수에 N의 제곱근을 int 자료형으로 담는다.

   (N의 제곱근을 이용하는 이유는 효율성을 위함이다. 예를 들어 36의 제곱근은 6이고 36의 약수들을 나열했을때 제곱근인 6을 기준으로 1과 36, 2와 18, 3과 12, 4와 12는 짝을 이루어서 36을 만들 수 있다. 그렇기 때문에 제곱근인 6을 기준으로 6보다 큰 약수들은 6보다 작은 약수들의 배수로 어차피 소수가 아님으로 걸러질 숫자들이다.)

3.  1은 소수가 아니기 때문에 1을 제외한 가장 작은 수인 2부터 m까지 소수 판별을 하기위해 반복문을 만든다. 

4. 만약 sieve(체)에서 i가 True라면 (소수가 맞다면)

5. i 들의 배수들은 소수가 아니기 때문에 sieve(체)에서 해당 숫자들은 False(소수가 아님)으로 변경한다. 이것을 N까지 판별하기 위해 반복문에서 범위는 N+1까지 이다. 

6. sieve(체)에서 True(소수가 맞음)인 숫자들만 result에 담는다. (sieve에서는 1이 True이지만, 애초에 1은 제외하고 판별을 했기 때문에, 1을 제외한 2부터 소수들을 result에 담는다.)

 

 

하나의 숫자 소수 판별

def solution(N):
	m = int(N ** 0.5)
    for i in range(2, m+1):
    	if N % i == 0:
        	return False
    return True

하나의 숫자가 소수인지 판별하는 방법은 에라토스테네스의 체 알고리즘과 비슷하다.

동일하게 제곱근 까지의 숫자들 중에 N이 나누어 떨어지는 숫자가 있다면 N은 소수가 아니기 때문에 False를 반환하고,

제곱근 까지의 숫자들 중에 N이 나누어 떨어지는 숫자가 없다면 N은 소수가 맞으므로 True를 반환한다.