[코딩테스트] 소수찾기 알고리즘, 에라토스네스의 체(python)

소수찾기 알고리즘

소수란,

• 1과 자기 자신을 제외한 숫자로 나누어 떨어지지 않는 숫자를 의미한다. (즉, 약수가 1, 자기자신 을 제외하고는 없음을 의미)

소수는 어떻게 찾을까?

효율적이지 못한 방법

1. 2부터 값의 이전 값 까지 숫자를 1 씩 올려가며 나눠 떨어지는지 확인을 하고, 나누어 떨어지는 값이 하나라도 없으면 소수로 판별한다.

• 문제점

  만약, 30 의 숫자가 있다고 하면,
  1, 2, 3, 5, 6, 10, 15, 30 의 약수들을 갖는다.

  30이 2 로 나누어 떨어지면, 15 로도 나누어 떨어지는 것을 확인한 것과 동일하다.

  이렇게 할 경우 판별하지 않아도 되는 값을 각각 한번씩 더 확인을 해야하는 경우가 생겨, 효율적이지 못한 방법인 것이다.

2. 2부터 값의 절반 값 까지 1을 올려가면 나누어 떨어지는지 확인을 한다.

• 문제점

  앞선 예 1, 2, 3, 5, 6, 10, 15, 30 에서 30의 절반 값은 15 이다. 하지만, 우리는 5 까지만 확인을 하면 되는데, 6 ~ 15 까지 쓸모 없는 확인을 하게 되기 때문에 효율적이지 못한 방법이다.

효율적인 방법

3. 2부터 찾는 값의 제곱근 까지 1씩 올려가며 나눠떨어지는지 확인을 한다.

• 이유:

  어떤 수를 정수 곱으로 표현 할 수 있으면 그 정수가 바로 약수 인데, 제곱근은 그 수를 곱으로 표현하는 방법의 중간 값을 나타내기 때문에 가장 효율적인 방법으로 숫자를 확인 할 수 있기 때문이다.

  예를들어, 30 의 제곱근은 약 5.47722557505 이다.

  즉, 실수가 약수가 될 수가 있다면,
  5.47722557505 이 30 의 약수가 되는데,

  5.47722557505 보다 큰 수는 그 전에 확인이 되기 때문에, 확인을 할 필요가 없게된다.

  ---

  코드

 def is_prime(num):
    max_length = int(num ** 0.5) + 1
    for i in range(2, max_length):
        if num % i == 0:
            return False

    return True

에라토스네스의 체

만약, 숫자 N까지 소수를 찾는 방법이다.

모든 숫자가 소수라고 가정을 하고, 2 부터 숫자 N 까지 1을 증가 시키며, 현재 확인하는 숫자가 소수가 아니라면 다음 값으로 넘어가고, 현재 숫자가 소수이면, 그 숫자의 배수들을 모두 소수 에서 제외시킨다.

코드

def sieve_of_eratos(n):
    sieve = [True] * (n + 1)
    max_length = int(n ** 0.5) + 1
    for i in range(2, max_length):
        if sieve[i]:
            for j in range(i + i, n + 1, i):
                sieve[j] = False

    return [i for i in range(2, len(sieve)) if sieve[i] != False]