[python] SWEA - 4698. 테네스의 특별한 소수

🤔문제 해결

• D3 | 소수

💨 에라토스테네스의 체를 이용해서 미리 소수들을 구한다.

💨 D 가 포함되면서 소수인 수를 찾는다.

 

💻소스 코드

# 테스트케이스마다 소수를 찾으면 시간초과가 발생하기 때문에 에라토스테네스의 체를 이용해 미리 소수들을 구해놓는다.
N = 10**6
def set_prime():
    for i in range(N+1):
        if prime[i] == 1:
            for j in range(i*2, N+1, i):
                prime[j] = 0

prime = [1]*(N + 1)
prime[0], prime[1] = 0, 0
set_prime()

for tc in range(int(input())):
    D, A, B = map(int, input().split())
    answer = []
    for i in range(A, B+1):
        if str(D) in str(i) and prime[i]:  # 숫자가 D를 포함하면서, 소수이면
            answer.append(i)

    print(f'#{tc+1} {len(answer)}')
 

📕문제 확인

출처: SW Expert Academy

SW Expert Academy