[Python] 소수

소수

2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수

import math
def is_prime_number(x):
	for i in range(2, int(math.sqrt(x))+1): # 2부터 x의 제곱근까지 확인
		if x % i == 0:
			return False
    return True

에라토스테네스의 체

2부터 N까지의 모든 자연수에 대한 소수 판별

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

아래는 프로그래머스에서 본 풀이인데, 시간은 더 오래걸리지만 간결하고 이해하기 쉽습니다.

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return list(num)

문제

1. 프로그래머스, 2단계, 소수만들기