[백준] 1929 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

에라토스테네스의 체

- 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘

- N보다 작거나 같은 모든 소수를 찾을 때 사용

- 시간복잡도는 O(NloglogN)으로 선형 시간에 동작할 정도로 빠르지만 메모리가 많이 필요하여 1,000,000 이내로 주어지는 경우에 사용한다. (1,000,000 -> 400만 번 정도의 연산)

 

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

array = [True for i in range(1000001)]
array[1] = 0

for i in range(2,int(math.sqrt(m))+1):
  if array[i] == True:
    j = 2
    while i*j <=m:
      array[i*j] = False
      j+=1
for i in range(n,m+1):
  if array[i]==True:
    print(i)

step1)

- M,N의 최대 범위인 100000을 고려하여 1000001 크기의 배열을 만든다 

- 이 배열은 소수인지 아닌지 확인하는 용도이다.

 

step2)

- 2부터 M의 제곱근까지 반복하면서 해당 수의 배수를 False로 만들어준다.

[point]

- 1은 소수가 아니기 때문에 제외한다.

- j = 2부터 시작하여, 자기자신은 제외한다. (소수가 아니라면 배수를 False로 만드는 과정을 통해 처리됨)

- M의 제곱근까지 반복을 진행한다. 

ex) 15의 약수는 1,3,5,15 인데 15의 제곱근인 3.xx 에서 정수형으로 바꾼 3까지만 확인해도 15가 소수가 아닌 것을 확인할 수 있기 때문이다.

-> 그래서 최대 수인 M의 제곱근까지 확인

 

step3)

- 찾고싶은 범위인 N~M에서 값이 TRUE인 인덱스 번호를 출력한다.