[백준] 1124번 언더프라임 문제! (silver 2

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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());
		int[] prime=new int[b+1];
		prime[0]=1;
		prime[1]=1;	
		for(int i=2; i<prime.length; i++) {
			if(prime[i]==1) {
				continue;
			}
			for(int j=i+i; j<prime.length; j+=i) {
				prime[j]=1;
			}
		}
		int div=2;
		int sum=0;
		int temp;
		int howMany=0;
		for(int i=a; i<=b; i++) {
			temp=i;
			div=2;
			while(true) {
				while(true) {
					if(temp%div!=0) {
						break;
					}
					temp/=div;
					howMany++;
				}
				if(div>temp) {
					break;
				}
				while(true) {
					div++;
					if(prime[div]==0) {
						break;
					}
				}
			}
			if(prime[howMany]==0) {
				sum++;
			}
			howMany=0;
		}

		bw.write(sum+"");
		bw.flush();
	}
}