[백준] 6219번 소수의 자격 문제! (silver 3

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int a=Integer.parseInt(st.nextToken());
		int b=Integer.parseInt(st.nextToken());
		String d=st.nextToken();
		int[] num=new int[b+1];
		num[1]=1;
		int count=0;
		
		for(int i=2; i<=b; i++) {
			if(num[i]==1) {
				continue;
			}
			for(int j=i+i; j<=b; j+=i) {
				num[j]=1;
			}			
		}
		
		for(int i=a; i<=b; i++) {
			if(num[i]==0) {
				if(String.valueOf(i).contains(d)) {
					count++;
				}
			}
		}
		
		bw.write(count+"");
		bw.flush();
		
	}
}
//에라토스테네스의 체 이용