[파이썬/python] 백준 - 6219 소수의 자격

문제

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

---

문제 설명

1. A와 B 사이의 소수가 숫자 D를 포함하는지 검사한다.
2. 숫자 D를 포함한 소수의 개수를 구한다. 

 

---

풀이

에라토스테네스의 채를 통해 소수를 찾은 후, A와 B 사이의 소수가 숫자 D를 포함하는지 확인 후 카운트한다.

1. 에라토스테네스의 채를 통해 2부터 B까지 소수를 전부 탐색한다.
2. A에서 B까지 탐색하면 해당 숫자가 D를 포함하는지 검사한다.
   1. 이 때 숫자를 스트링으로 변경하여 문자열 내 D 문자가 포함되어 있으면 카운트한다.

---

코드

import sys
input = sys.stdin.readline

def p():
    board = [i for i in range(b+1)]
    board[1] = 0
    for i in range(2,b+1):
        for j in range(2*i,b+1,i):
            board[j] = 0
    return board

a,b,d = map(int,input().split())
primes = p()
cnt = 0
for i in range(a,b+1):
    if primes[i] and str(d) in str(primes[i]):
        cnt += 1
print(cnt)

---

시간복잡도

• 에라토스테네스의 채 시간복잡도는 $log_{log_n}$이다.
• 이 때 N의 최대 $4*10^6$이므로 약 $O(log_{log_{4*10^6}})$의 시간복잡도가 소요된다.