PS/백준

[BOJ] 백준 6219번 : 소수의 자격 (JAVA)

제이온 (Jayon) 2020. 11. 13.

문제

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

 

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

 

소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다.

 

소수의 예로는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.. 가 있다.

 

 

입력

세 정수 A, B, D가 주어진다.

 

 

출력

주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.

 

 

제한

1 ≤ A ≤ B ≤ 4,000,000

 

B ≤ A + 2,000,000

 

 

풀이

간단한 소수 판정 문제였습니다.

 

 

B의 최대 범위가 4,000,000이므로 굳이 에라토스테네스의 체를 쓰지 않아도 $$2 <= i <= \sqrt{n}$$에 해당하는 i로 n을 나누면서 소수를 판정해도 풀 수 있었습니다.

 

따라서 A부터 B까지 하나 하나 소수 판정을 하면서 어떤 수 n이 소수라면, n의 자리 수에 해당하는 값들이 D와 같은지 다시 하나 하나 확인하면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

댓글

추천 글