에라토스테네스의 체 (with python3)

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.

소수를 판별 함수 부분 1:

def findprimnum(num): #소수인지 판별
    for i in range(2, num):
        if num%i==0:
            return 0;
    return num;

자연수 n에 대해 그 이하의 소수를 찾아내는 데 최적화된 알고리즘으로
위 코드보다 훨씬 빠르기 때문에 소수가 필요할 때 사용하면 좋을 것 같다.

작동방식은 아래 화면과 같다.

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]

+) 약수 구할 때 : 1부터 sqrt(n)까지 n의 약수가 없다면 n은 소수이다.

응용문제:
https://www.acmicpc.net/problem/6588

참고:
https://hyelie.tistory.com/entry/%EC%95%BD%EC%88%98-%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

sqrt부분 이해 참고:
https://devlibrary00108.tistory.com/87