소수 찾기

알고리즘

1. 해당 수의 제곱근을 찾는다
2. 제곱근보다 작은 수 중에서, 1과 자기 자신을 제외하고 나누어 떨어지는 수가 있는지 확인한다
   • 있다면, 제외
   • 없다면, 소수

해당 알고리즘에 대한 설명

어떤 수를 N이라고 했을 때, N에 대한 소수 여부를 판단하려면 일반적으로 N-1까지의 모든 수에 대해서 나누어 떨어지는지 확인을 해볼 것이다.

하지만 이런식으로 구현하게 되면, 대체로 시간초과가 뜨기 마련이다. 따라서 loop를 최소화 시킬 수 있는 다른 방법이 필요하다.

N이 자연수 a,b로 나눠질 수 있는 수라고 가정하자, 그리고 N에 대한 제곱근을 r이라고 가정하자. N = a*b = r*r가 성립하게 된다.

이때, (a,b,r)의 관계는 세가지로 분류된다.

1. a > r > b
2. b > r > a
3. a = b = r

따라서, N이 두개의 자연수로 나눠질 수 있는 수라면, 다시 말해 소수가 아니라면, 제곱근 r보다 작거나 같은 수 중에서 r과 나눴을 때 나누어 떨어지는 수가 있다는 것을 확인할 수 있다.

더 직관적으로 보자면, N=100이라고 할 때, 100을 두개의 자연수의 곱으로 나타낼 수 있는 방법은 다음과 같다.

• 1 * 100
• 2 * 50
• 4 * 25
• 5 * 20
• 10 * 10
• 20 * 5
• 25 * 4
• 50 * 2
• 100 * 1

위의 경우의 수 중에서 100의 제곱근 즉, r=10이 되고 각각의 두 수는 a,b가 되는 것이다.

맨 위에서 설명했던 알고리즘을 여기에 적용해 보면, 직관적으로 잘 이해가 될 것이라고 생각한다.

# 소수 확인 소스코드

num = int(input())
ans = True

def check(num):
    for i in range(2,int(num**0.5+1)):
        if num%i == 0:
            return False
            
ans = check(num) # 소수이면 True, 아니면 False