AngelPlayer`s Diary

링크

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

 

 

 

 

문제 해석

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

 

 

입력

첫 번째 줄 : a b d

  a : 시작 값

  b : 마지막 값

  d : 포함할 숫자

 

 

출력

d를 포함하는 숫자의 개수

 

 

 

풀이 & 코드 해석

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

 

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

https://angelplayer.tistory.com/391

 

[알고리즘] 소수 (Prime)

소수 구하기 - 숫자 N의 소수 판정 방법 1 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 - 에라토스테네스의 체 사용하기 각 수는 임의의 값 n * n 제곱하여 나오는 n보다 큰 값을 ( i

angelplayer.tistory.com

 

 

 

이 문제에서도 에라토스테네스의 체를 이용하여 우선 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

공유하기

facebook twitter kakaoTalk kakaostory naver band