본문 바로가기

문제 풀이/Baekjoon

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

문제 출처 - Baekjoon Online Judge

문제는 여기

 

6219번: 소수의 자격

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

www.acmicpc.net

[문제] 

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 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;
	}
}