소수 판별 알고리즘

내가 주로 소수를 판별하는데 사용할 방법은 √  를 활용한 방법이다.
이 방법에 대해서 원리가 어떻게 되는지 기억하고 나중에도 떠올릴 수 있도록 하자!.

 

🖥️ 동작 원리

기본적으로 소수인지 알 수 있는 방법으로는 N이라는 수가 주어졌을 때 N과 1을 제외해서 이 N의 나머지를 0으로 만드는 값이 없다면 소수이다. 

• 즉 11이라는 수가 주어졌을 때 1과 11을 제외하고 11을 나눌 수 없기에 11은 소수이고 12는 1, 2, 3, 4, 6으로 나뉘기에 소수가 아니다.

그렇기에 위 원리를 통해서 소수를 판별하는 식은 아래와 같다.

🌈 파이썬 코드

def is_prime_number(N):
  for i in range(2, N):
    if N % i == 0:
      return False
    reutrn True

• 2부터 시작하는 이유는 1은 소수가 아니기에 2부터 시작하면 된다.

하지만 이런식으로 문제를 구하려면 시간복잡도가 log(N)이며 N의 값이 커질수록 무한정 증가하기에 좋은 코드가 아니다.

그렇기에 소수를 판별하기에 시간복잡도가 훨씬 나은 방법으로 소수가 아닌 값은 약수를 가진다는 것에 주목하면 된다.

N = 40,
1 2 4 5 8 10 20 40
40이라는 값이 주어졌을 때 약수는 위와 같은 값으로 주어진다. 여기서 약수의 특징으로 볼 수있는 것이 대칭되는 값을 곱한다면 N이 된다는 것이다(1 * 40, 2 * 20, 4 * 10, 5 * 10) 그렇게 중심이 되는 8을 찾을 수 있다면 8보다 작은 값에서 약수가 하나라도 나온다면 8보다 큰 값에서 대칭되는 N을 만들 수가 존재한다는 얘기가 된다.

위 내용을 바탕으로 우리는 약수를 가진 수는 소수가 아니라는 것을 알 수 있다. 여기서 중심되는 값을 찾는 방법이 바로 √ 를 활용한 방법이다. 주어진 값 N의 제곱근까지만 우리는 계산을 하게 되면 자연스럽게 제곱근보다 큰 값에서는 대칭되는 약수가 존재한다는 것이되기에 이를 바탕으로 우리는 소수를 찾을 수 있다.

 

🌈 최종 코드

문제: 백준 2518번 소수 (브론즈 2)

import math
def solution():
    N = int(input())
    values = list(map(int, input().split()))
    count = N
    for value in values:
        if value == 1:
            count -= 1
            continue
        for i in range(2, int(math.sqrt(value)) + 1):
            if value % i == 0:
                count -= 1
                break
    return count
print(solution())

• 제곱근을 구하기 위해서 math.sqrt()를 이용했지만 이렇게 하는 것이 아닌 i를 제곱하는 방식도 있었다.

def is_prime(num):
    if num<=1:
        return False
    i=2
    while i*i<=num:
        if num%i==0:
            return False
        i+=1
    return True

• 해당 함수에서는 i를 제곱하여 동일한 결과를 낼 수 있기에 어느 것을 사용해도 괜찮을 것 같다