Facebook Hacker cup 2015, Round 1 Solution

Facebook Hacker cup 2015, Round 1 Solution

Homework

The problem introduces the term primacity as:

Let $I_{m}$ an integer positive and $P_{n}$ a prime number, the primacity of $I_{m}$ is the amount of $P_{n}$ which divides it.

For example: Let $I = 550$, its primacity is $3$ becuase ${2, 5 \mbox{ and } 11}$ divide it.

The problem ask us: Given 3 numbers $A, B \mbox{ and } K$, how many integers in the inclusive range $[A, B]$ have a primacity of exactly $K$

Constraints:

$1 \leq T \leq 100$ , Let $T$ the number of test cases
$2 \leq A \leq B \leq 10^7$
$1 \leq K \leq 10^9$

Clearly, we need to have a list of primes numbers for used later, we can use a modified of the Sieve of Eratosthenes. Let $L$ an array with length $10^7+1$ with initialized values of 0, the principle idea here is that each time that we found a $P_{n}$ in the sieve we increment by $1$ to $L[P_{n}]$ thought $L[iP_{n}]$, where $i$ is a number lesser than $\frac{10^7}{P_{n}}$. Then, when we ask if $I_{m}$ in the interval $[A, B]$ has primacity $K$, just we need to check out if $I_{m}==L[I_{m}]$. After that only we increment an $r$ by 1 each time that last statement is true for get the final answer. The complexity of this task is the same than the Sieve: $\mathcal{O}(n\log{}n)$ for the integers $1 \mbox{ to } n$.

Read full article from Facebook Hacker cup 2015, Round 1 Solution