[Python] 백준 6219. 소수의 자격 +) 에라토스테네스의 체

문제

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

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.

입력

세 정수 A, B, D가 주어진다.

출력

주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.

제한

• 1 ≤ A ≤ B ≤ 4,000,000
• B ≤ A + 2,000,000

---

풀이

이건 소수를 구하는 에라토스테네스의 체를 알고 사용하면 금방 풀 수 있는 문제였다. 

에라토스테네스의 체는 예시로 10 이하까지의 소수를 찾는다고 했을때

2 -> 2, 4, 6, 8, 10

3 -> 3, 9

... 이런 식으로 특정 수의 배수를 다 지워주면서 빠르게 소수를 찾아낼 수 있는 방식이다.

(체를 치듯이 수를 걸러내자~)

 

이를 코드로 나타내면

for i in range(2, b+1):
    if isPrime[i]:
        for j in range(i+i, b+1, i):
            isPrime[j] = False

 

이렇게 나타낼 수 있다. A~B까지 범위에서 D를 포함하는 소수의 개수를 구하는 것이기 때문에 일단 B+1 범위까지 에라토스테네스의 체를 활용해서 소수가 아닌 수들을 전부 False로 바꿔주는 코드이다.

 

이후에 True로 되어있는, 즉 소수인 수들 중 D를 포함하는 개수를 세서 출력하면 되는 문제였다.

 

import sys
input = sys.stdin.readline

a, b, d = map(int, input().rsplit())
isPrime = [True] * (b+1)
cnt = 0

isPrime[0] = False
isPrime[1] = False

for i in range(2, b+1):
    if isPrime[i]:
        for j in range(i+i, b+1, i):
            isPrime[j] = False

for i in range(a, b+1):
    if isPrime[i] and str(d) in str(i):
        cnt += 1

print(cnt)

 

i+i인 이유는, 소수인 수(isPrime[i])에서 이후에 나오는 수들(i+i, i+i+i ...) 들은 이제 소수가 아니므로 해당 값들을 False로 바꿔주는 구조이기 때문이다. 

 

시간복잡도

에라토스테네스의 체가 보통 O(N log log N)이고 밑에 d를 찾는 부분은 대충 O(n)일 것 같아서...

결과적으로는 O(n)이지 않을까 싶다.