SW Expert Academy // 4698

SW Expert Academy 4698번 "테네스의 특별한 소수" 문제입니다.

TC = int(input())
 
n=1000000
a = [False,False] + [True]*(n-1)
primes=[]
 
for i in range(2,n+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            a[j] = False
                 
for tc in range(1, TC + 1):
    D,A,B = map(int, input().split())
    count = 0
    for e in primes:
        if A <= e <= B:
            while e:
                if e%10 == D:
                    count += 1
                    break
                else:
                    e //= 10
    print("#%s"%tc, count)

A 이상 B 이하의 소수들 중에서 숫자 D를 포함한 테네스의 특별한 소수의 개수를 구하는 문제다.

 

에라스토테네스의 체로 구한 소수 리스트를 탐색하면서 A이상 B이하의 수를 다룬다.

 

그리고 10으로 나눈 나머지를 사용해서 D가 포함되어 있는지 아닌지를 확인한 후 포함되어 있다면 카운트를 1 증가시킨다.