[SWEA] 4698. 테네스의 특별한 소수

문제

테네스는 소수를 좋아한다. 소수란 1과 자기 자신만으로 나뉘어 떨어지는 숫자로 작은 것부터 나열하면 2, 3, 5, 7, 11, 13, 17, 19, 23, …같은 수들이 있다.

또한 테네스는 D를 포함하는 숫자도 좋아한다. 그렇기에 소수가 D를 포함하면 더욱 더 좋아하여 특별한 소수라고 부르기로 했다.

예를 들어 D = 3이면 3, 13, 23, … 같은 소수들이 3을 포함하였으므로 테네스는 이런 숫자들을 특별한 소수라고 부를 것이다.

D가 주어질 때, A이상 B이하의 수 중에서 특별한 소수인 것들의 개수를 구하는 프로그램을 작성하라.

 

풀이방법

D, A, B가 입력될 때마다 A부터 B까지의 소수를 구하면 시간초과가 발생한다.

 

따라서 1부터 B의 최대값 1000000까지 에라토스테네스의 체를 이용해 소수를 먼저 구한다.

 

그런 다음 D, A, B가 입력될 때, A이상 B이하의 소수 중에 자릿 수에 D를 포함하는 소수를 찾는다.

 

소스코드

package samsung;

import java.util.*;

public class s_4698 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		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++;
			}
		}
		
		for(int t = 1; t <= tc; t++) {
			int d = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			int cnt = 0;
			if(a == 1)
				a = 2;
			for(int i = a; i <= b; i++) {
				if(arr[i] == 0) {
					String s = String.valueOf(i);
					for(int j = 0; j < s.length(); j++) {
						if((s.charAt(j) - '0') == d) {
							cnt++;
							break;
						}
					}
				}
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}