[백준] 6219번 소수의 자격

💡문제접근

• A와 B를 포함한 범위 내에서 숫자 D를 포함하면서 소수를 만족시키는 수의 개수를 구하는 문제다. 이 때, 숫자 D는 한 자리 숫자이다.

💡코드(메모리 : 62504KB, 시간 : 1188ms)

import sys
input = sys.stdin.readline

A, B, D = map(int, input().strip().split())

prime_number = [True] * (B+1)
prime_number[0] = False
prime_number[1] = False
for i in range(2, B+1):
    if prime_number[i]:
        for j in range(i*i, B+1, i):
            prime_number[j] = False

cnt = 0
for i in range(A, B+1):
    # 조건1 : 소수를 만족시켜야함
    if prime_number[i]:
        # 조건2 : 숫자 D가 해당 소수에 몇 개가 포함되어있느냐?
        if str(D) in str(i):
            cnt += 1
print(cnt)

💡소요시간 : 17m