1929 소수 구하기

문제

주어진 두 수 사이의 소수를 모두 출력하는 문제이다.
(M <= x <= N )

Link: 소수 구하기

코드

import sys
import math
sys.stdin = open("../input/1929.txt", "r")

#입력받기
start, end = map(int, input().split())
#0 부터 검사하는 수 까지 bool 배열을 만든다 arr[i] = true -> i가 소수라는 뜻
arr = [True for i in range (0, end+1)]
#0과 1을 예외처리한다.
arr[0] = False
arr[1] = False
#소수를 검사하는 범위를 지정한다.  루트(최댓값) -> 내림 
max = math.floor(math.sqrt(end+1))

#검사 aristoteles의 채
for i in range(2, max+1):
    x = i+i
    while(x < end+1):
        arr[x] = False
        x += i

#출력하는 부분
for i in range(start, len(arr)):
    if(arr[i]):
        print(i)

사용된 개념

1. 아네스토테네스의 채
2. 소수

해설

1. n, m이 주어지면, 0 ~ M 까지 그 수가 소수인지 아닌지를 나타내는 배열 arr을 만듭니다.

2. 소수를 판별할때는 자신의 루트 값 전까지 판별하면 되는데 그 이유를 예시로 들면 100은 10 이상의 곱으로 표현할 경우, 10보다 작은 수가 곱해진다. 따라서 이미 for문이 돌아가서 검사가 되었으므로 그 다음은 무의미하다.

3. for문이 돌면서 소수가 아닌 수들을 지워나간다.
   1, 100이 들어왔을 경우,
   i=2) 4, 6, 8, .... 96, 98, 100
   i=3) 6, 9, 12, ... 93, 96, 99
   .
   .
   .
   i=10) 20, 30, 40, ... 100
   순으로 돌면서 소수가 아닌 두 수의 곱으로 표현 가능한 수들을 지워나간다.

4. 마지막으로 start 부터 end + 1 범위에 있는 소수들을 출력한다.

Today I Learned

아네스토테네스의 채는 메모리를 많이 쓴다는 단점이 있다.
하나의 수를 판별하는데 있어서는 사용하면 안된다.