소수 구하기

백준 1929번 문제입니다.

📌 문제 설명

상셰 설명: https://www.acmicpc.net/problem/1929

• M N의 형태로 주어지는 입력을 받아 M이상 N이하의 소수를 모두 출력한다.
• 출력은 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

📌 문제 풀이

m,n = map(int, input().split())

for i in range(m,n+1):
    if i==1:
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j==0: #약수가 존재함 -> 소수가 아님
            break #더 이상 볼 필요 없음
    else:
        print(i)

이 문제는 문제만 읽었을 때는 간단하다. 주어진 범위 내의 수를 모두 돌면서 1을 제외하고 나누어 떨어지는 수가 있는지 없는지 확인하면 된다. 하지만 시간초과로 정답을 맞출 수 없다. 그래서 사용하는 방법이 에라토스테네스의 체(소수 구하기)이다.

💡 에라토스테네서의 체

• 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 가장 간단하고 빠른 방법
• 만약, 1~ 20 사이의 소수를 찾는다고 가정해 보자.
  
• 가장 먼저 소수도 합성수도 아닌 유일한 자연수 1을 제거한다.
  
• 2를 제외한 2의 배수를 제거한다. (2는 소수가 되지만, 2의 배수는 2로 나누어 떨어지기 때문에 소수가 될 수 없다.)
  
• 3을 제외한 3의 배수를 제거한다. (3은 소수가 되지만, 3의 배수는 3으로 나누어 떨어지기 때문에 소수가 될 수 없다.)
  
• 4의 배수는 이미 지워졌기 때문에 (2의 배수에서) 2, 3 다음 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거한다.
  
• 마지막으로 7을 제외한 7의 배수를 제거한다.
  
• 8의 배수, 9의 배수, 10의 배수 등은 지울 필요 없다. (이미 2, 3 배수에서 지워졌기 때문이다.)
• 11 이상의 소수들의 배수부터는 지우지 않아도 된다. (100이하 자연수 중에서 11의 배수는 1~9사이의 값을 곱한 것인데 모두 1~9사이의 배수이다.)
• 위의 순서처럼 남은 것들의 2배수, 3배수, n배수를 지우다보면 소수만 남는다.
  📂 출처: 에라토스테네스의 체

<코드풀이>

1. if i ==1: continue
   1은 소수가 될 수 없으므로 제외한다.

2. for j in range(2 ,int(i**0.5)+1)
   : 2~제곱근 사이의 수로 나누어 떨어진다면 종료 -> 다음 수 확인
   범위 내의 수의 제곱근을 구해, 그 제곱근과 같거나 작은 수로 나누어 떨어지면 제거할 수 있다. 특정 수의 약수들은 대칭하여 곱을 이루기 때문이다.
   예를 들어 18의 약수는 1, 2, 3, 6, 9, 18이고 1*18, 2*9, 3*6으로 서로 대칭을 이룬다. 따라서 이런 경우에는 3까지만 확인하면 된다. (18의 제곱근은 18 ** 0.5 = 4.xx ... 이고, 이 제곱근보다 같거나 작은 수까지만 나눠보고 나누어 떨어지는게 있는지 없는지 확인하면 된다.)

3. else
   나누어 떨어지지 않거나, for문이 끝난다면 else문에 해당 값 출력한다.