Python으로 알고리즘 공부 06. 소수 (Prime number)

소수판별1. 에라토스테네스의 체

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

• N보다 작은 소수들을 찾으려면, 2보다 크거나 같고 ​보다 작은 소수의 배수들만 지우면 된다.

• 예를 들어, 120보다 작은 소수들을 모두 찾고 싶다면, ​ 이므로 2, 3, 5, 7의 배수만 지우면 남은 수는 모두 소수가 된다.

• 작은 수의 소수를 판별하는 데 유용하다.

def is_prime(num):
    if num <= 1:
        return False
    
    i = 2
    while i*i <= num: 
        #여기서 i가 소수인지 알 수 있으면 더 빠르게 판별 가능.
        #is_prime(i)로 체크하면 n팩토리얼의 복잡도를 가진다.
        if num % i == 0:
            return False
        i+=1
    return True