### PROBLEM LINK

### DIFFICULTY

SIMPLE

### PREREQUISITES

### PROBLEM

A number is called a **K-prime** if it has **K** distinct prime factors.

Find the number of **K-prime** numbers between some given **A** and **B**, inclusive.

### QUICK EXPLANATION

Let us look at a simple implementation of the **Sieve of Eratosthenes**.

isPrime[N] = { YES } for i = 2 to N if isPrime[i] = YES j = 2 while i*j ≤ N isPrime[i*j] = NO j += i

**Sieve of Eratosthenes** has the wonderful property of **iterating through all the multiples of a prime number, for each unique prime number below N**. This means that the number of times the algorithm above marks a number **not prime** is equal to the number of unique prime factors of the number!

### EXPLANATION

Let us maintain the number of times the Sieve of Erotosthenes algorithm would mark an item as **not prime**. This maintained in the array **marked**.

marked[N] = { 0 } isPrime[N] = { YES } for i = 2 to N if isPrime[i] = YES marked[i] = 1 // each prime is its own single factor j = 2 while i*j ≤ N isPrime[i*j] = NO marked[i*j]++ j += i

Now, for any given range **[A,B]** and value **k**, we can iterate through **marked**. If the value in marked is equal to **k** then we know that the number has exactly **k** distinct prime factors.

The complexity of **Sieve of Eratosthenes** is equivalent to the number of times the innermost statement is executed. This is equal to the sum of the number of distinct prime factors for each number below **N**. We know that a number cannot have more than **log N** prime factors. In fact, the complexity of **Sieve of Eratosthenes** is equal to **O(N log log N)**.

There is one problem in our solution though. We are iterating between **A** and **B** for each input. It is given that there might be as many as **10000** inputs to be processed within a single second.

You will notice that the limit on possible values of **k** is very small. This can be exploited. Even if there were no limits on **k**, the maximum possible value in marked would be **7**.

You can build a table to store the number of times some **k** occurs in **marked** before each position **i**, for each **k**.

table[5][N] = { 0 } for i = 2 to N for j = 1 to 5 table[j][i] = table[j][i-1] v = marked[i] if 1 ≤ v ≤ 5 table[v][i]++

Now the answer for some range **[A,B]** and value **k** can be found in constant time form **table**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.