10/18 소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수를 구하는 문제이다.

내 풀이.

def prime(n) :
    answer = 1
    if n == 2 :
        return answer
    
    for i in range(3, n + 1, 2) :
        is_prime = True
        for j in range(2, int(i ** 0.5 + 1)) :
            if i % j == 0 :
                is_prime = False
                break
		if is_prime :
            answer += 1
            
	return answer

2는 소수 중 유일한 짝수이므로 n이 2일경우 먼저 처리한다.

짝수인 경우가 제거됐으므로 다음부터는 3 이상의 홀수만 생각하면 된다. 약수가 있는지 없는지는 주어진 숫자의 sqrt(n)보다 작은 수가 약수인지를 확인하면 된다. 그러므로 range의 범위는 2 ~ int(i ** 0.5 + 1)로 설정해준 뒤 나누어 떨어지는 수가 있으면 boolean 변수는 False이고 나누어 떨어지는 수가 없다면 초기화한 boolean 변수가 True이므로 소수로 판별되게 된다.

다른 사람의 풀이

def solution(n) :
    num = set(range(2, n + 1)) # 2이상 n이하의 모든 자연수
    
    for i in range(2, n + 1) :
        if i in num : # num에서 처리하지 않은 가장 작은 수
            num -= set(range(2 * i, n + 1, i)) # i를 제외한 i의 배수를 제거한다. 2 * i부터 n + 1까지 i 간격에 있는 모든 수 제거
	return len(num)

이 풀이는 에라토스테네스의 체를 이용해 작성한 코드이다.

에라토스테네스의 체

• 에라토스테네스의 체는 소수 여부를 판단할 때 사용하는 알고리즘이다.
• 동작 과정
  1. 2부터 N까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
  3. 남은 수 중에서 i를 제외한 i의 배수를 모두 제거한다.
  4. 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.