Rasta and Tavas

Rasta calls a number like a Tavas if and only if 1 ≤ a ≤ n and the sum of all primes (like p) that p | a is exactly equal to k.
He asks you to find the number of Tavases.

Input format

The first and only line of input contains two integers, n and k (1 ≤ n, k ≤ 10⁶).

Output format

Print a single integer, the number of Tavases.

---

Sample Input

20 7

Sample Output

3

Explanation

The only Tavases are 7, 10 and 20.

---

Time Limit: 2 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code:  

 

/* IMPORTANT: class must not be public. */

/*
 * uncomment this if you want to read input.*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map.Entry;


class TestClass {
    public static void main(String args[] ) throws Exception {
        /*
         * Read input from stdin and provide input before running
*/
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String input[]= new String[2];
        input = line.split(" ");
        printTavas(Integer.valueOf(input[0]),Integer.valueOf(input[1]));

       
    }
   
   
   public static void printTavas(int n, int k){
    int pr[]=new int[n+2];
    for(int i=2;i<=n;i++){
        if(pr[i]==0){
            for(int j=i;j<=n;j+=i){
                pr[j]+=i;
            }
        }
    }
    int count=0;
    for(int i=0;i<=n;i++){
        if(pr[i]==k)
            count++;
    }
    System.out.println(count);
}
}