KPRIME - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Sieve of Eratosthenes

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.

11 Likes
2

Hello,

Very good editorial and it exploited some nice properties of the Sive of Erathostenes I wasn’t aware of at all :slight_smile: Thank you for this!!

In my solution I just precomputed both the prime numbers using trial divison and I did the same for the prime factors…

After preprocessing both of these two things, solutions run instantly on any given input and it is also possible to have AC using only simple division if one is aware of the power of precomputation :slight_smile:

Best regards,

Bruno

3 Likes
3

I generated the list of primes using Sieve of Atkin.

Now, I have 5 lists, the first one for numbers with 1 distinct prime factor, the second one with 2 distinct factors, and so on, Since these are the values k can take… Anyway, we will not need more than 6 lists, as there won’t be any numbers with 7 distinct factors. (Why? the product of the smallest 7 prime numbers exceeds the maximum possible value A or B can take.)

Now, for each number, the number of factors are calculated and i added to the appropriate list. Trial division, with the prime list computed is used here.

Once these preprocessing is over, it is straightforward to just count how many numbers in the kth list falls between A and B.

Here is the link to my AC solution: http://www.codechef.com/viewplaintext/2326735

2 Likes
4

I used Segment Trees to solve this problem.I have just maintained five segment trees for each k :slight_smile:

1 Like
5

In implementation of the Sieve of Eratosthenes, isn’t ’ j ’ should be incremented by 1 instead of ‘i’?

2 Likes
6

No, because we are marking multiples of ‘i’ as not prime. So, ‘j’ must be incremented by ‘i’

7

actually it should be 1

8

In this case,it should be 1.

9

Someone Please explain the memoization part done using table[][].

10

how is the above implementation of sieve marking 9 as not prime in the range 2 to 15? It is skipping 9!
when i=3 and j=2, 6 gets marked as not prime, j becomes 5 as j+=i, so 15 is the next number to be marked as non-prime! Shouldn’t prime[j]=No be done instead of prime[i*j] ?

11

Can somebody please explain to me, why my code passed within the time limit when I didn’t even make a table to store all the values of ranges? I just brute forced it and calculated for every range the number of k primes. My solution

12

@akulgoel

You’d had got timeout had the sieve function been inside the while loop in main function :stuck_out_tongue:

What you did was that you created the sieve first, precomputed your answer and then simply returned it after taking inputs in while loop. Pre-computation is a good way to solve such problems.
Eg- Problems involving printing the i’th prime number etc. Precomputation helps here.

(Besides I don’t think problem setter wants us to get bald by pulling hair out on a ‘cakewalk’ problem :p. I bet, the test cases would had been way tougher had the problem been classified as ‘hard’ or ‘moderate’ )