[SWEA] - 4698. 테네스의 특별한 소수 (D3)

[문제]

테네스는 소수를 좋아한다. 소수란 1과 자기 자신만으로 나뉘어 떨어지는 숫자로 작은 것부터 나열하면 2, 3, 5, 7, 11, 13, 17, 19, 23, …같은 수들이 있다.
또한 테네스는 D를 포함하는 숫자도 좋아한다. 그렇기에 소수가 D를 포함하면 더욱 더 좋아하여 특별한 소수라고 부르기로 했다.
예를 들어 D = 3이면 3, 13, 23, … 같은 소수들이 3을 포함하였으므로 테네스는 이런 숫자들을 특별한 소수라고 부를 것이다.
D가 주어질 때, A이상 B이하의 수 중에서 특별한 소수인 것들의 개수를 구하는 프로그램을 작성하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 세 정수 D, A, B(1 ≤ D ≤ 9, 1 ≤ A ≤ B ≤ 106)가 공백으로 구분되어 주어진다.

[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 특별한 소수의 개수를 출력한다.

문제 풀기

4698. 테네스의 특별한 소수

 

---

[풀이]

• D, A, B를 입력받을때마다 A~B까지의 소수를 구하면 시간 초과가 발생하기 때문에 1부터 최댓값까지의 소수를 먼저 구해 저장해둔다.
• 그다음 소수중에 자릿수에 D를 포함하는 소수를 찾는다.

import java.util.Scanner;

class Solution {	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 에라토스테네스의 체를 이용한 소수 찾기
		int[] arr = new int[1000001];
		for(int i=2; i<arr.length; i++) {
			int j = 2;
			while(true) {
				if(i * j > 1000000) break;
				arr[i*j] = 1;
				j++;
			}
		}
		
		int t = sc.nextInt();

		for(int tc=1; tc<=t; tc++) {
			int d = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			int cnt = 0;
			
			// 1은 소수가 아니므로 제외하고 탐색!
			if(a==1) a=2;
			
			for(int i=a; i<=b; i++) {
				if(arr[i] == 0) {
					String s = String.valueOf(i);
					if(s.contains(String.valueOf(d))) cnt++;
				}
			}
			
			System.out.format("#%d %d\n", tc, cnt);
		}
	}
}