[BOJ / 백준] 6219 소수의 자격 (S3 / 수학) - Python

링크

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

 

 

 

 

문제 해석

a에서 b사이의 소수 중 d를 포함하는 수가 몇 개인지 구하라

 

 

입력

첫 번째 줄 : a b d

  a : 시작 값

  b : 마지막 값

  d : 포함할 숫자

 

 

출력

d를 포함하는 숫자의 개수

 

 

 

풀이 & 코드 해석

소수를 구하는 가장 빠른 방법은 에라토스테네스의 체입니다.

 

에라토스테네스의 체를 구현하는 방법은 아래 링크에 설명되어 있습니다.

https://angelplayer.tistory.com/391

[알고리즘] 소수 (Prime)

 

 

 

이 문제에서도 에라토스테네스의 체를 이용하여 우선 a~b까지의 소수를 판정한 후, 소수들이 조건에 부합하는지 체크하면 해결할 수 있습니다.

 

 

 

 

코드

a, b, d = list(map(int, input().split()))

# true == 소수가 아님
isPrime = [False] * (b + 1)

isPrime[0] = True
isPrime[1] = True

ans = 0

for i in range(2, b + 1):
    if isPrime[i] == False:
        if i >= a:
            str_i = str(i)
            for k in range(len(str_i)):
                if str_i[k] == str(d):
                    ans += 1
                    break

        for j in range(i * i, b + 1, i):
            isPrime[j] = True

print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java