[백준/Python] 6219번: 소수의 자격

 

1. 문제 

 

6219번: 소수의 자격

 

2. 해결방법 

N의 크기가 작았기에 

에라토스테네스의 체 알고리즘을 사용하였다. 

[ 알고리즘/ Python ] 소수 구하기 : 에라토스테네스의 체

 

 

3. 코드 

A = [False, False] + [True]*4000000

for i in range(2, 4000000):
    if A[i]:
        for j in range(i+i,4000000, i ):
            A[j] = False

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

소수를 판정하는 문제에서 n이 10^6 정도로 주어지면 에라토스테네스의 체를 사용하여 간단하게 풀 수 있다!