문제 출처 - Baekjoon Online Judge
문제는 여기
[문제]
농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.
베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.
소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.
[입력]
세 정수 A, B, D가 주어진다.
[출력]
주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.
[풀이]
1. 에라토스테네스의 체를 사용해 Max 범위의 배열에 맞춰 소수를 구해준다.
2. A~B까지 for문을 돌면서 소수인지를 체크한다.
3. 범위 사이에 포함되면서 소수라면 check를 통해 d가 포함이 되는지를 확인해준다.
4. 포함이 된다면 cnt를 증가시켜주고 아니라면 넘어간다.
[접근]
1. 에라토스테네스의 체를 사용해서 소수배열을 구해주고 소수인지 판단하는 데 사용을 하면 시간이 많이 단축된다.
2. for문을 돌리면서 소수인지를 판단해주고 해당 소수를 계속해서 10으로 나눠주고 10으로 나눴을 때의 나머지가 D인지를 확인해서 D라면 카운트를 증가시켜준다.
[코드]
import java.util.*;
import java.io.*;
public class Main_S4_6219 {
static int a;
static int b;
static int d; // 포함해야 하는 수
static int max = 4000001;
static boolean prime[] = new boolean[max];
static int cnt;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 에라토스테네스의 체를 사용해서 소수 배열 구성
Arrays.fill(prime, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i < max; i++) {
if (prime[i]) {
for (int j = i * i; j < max; j += i) {
prime[j] = false;
}
}
}
// 입력받기
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
// a~b사이 탐색
for (int i = a; i <= b; i ++) {
if (prime[i]) { // 소수라면
if (check(i)) // 체크 함수의 return이 트루라면
cnt++; // cnt 증가
}
}
System.out.println(cnt);
}
// d가 포함되는 지 확이하는 함수
static boolean check(int n) {
while (n > 0) { // n을 계속 나눌것이기 때문에 n이 0보다 클 때까지 반복한다.
int num = n % 10; // 1의 자리에 해당하는 한 자리의 숫자
n /= 10; // 10으로 나눈다.
if (num == d) // 만약 나머지가 d와 같다면 d를 포함하는 것이기 때문에 return true
return true;
}
// while을 다 돌았는데 return되지 않았다면 포함하지 않는 것이니까 return false
return false;
}
}
'문제 풀이 > Baekjoon' 카테고리의 다른 글
[백준] S5 5555번 반지 (JAVA) (0) | 2021.12.03 |
---|---|
[백준] S5 1251번 단어 나누기 (JAVA) (0) | 2021.12.02 |
[백준] S2 4948번 베르트랑 공준 (JAVA) (0) | 2021.11.30 |
[백준] S5 2204번 도비의 난독증 테스트 (JAVA) (0) | 2021.11.27 |
[백준] S4 1822번 차집합 (JAVA) (0) | 2021.11.27 |