PROBLEM LINKDIFFICULTYSIMPLE PREREQUISITESPROBLEMA number is called a Kprime if it has K distinct prime factors. Find the number of Kprime numbers between some given A and B, inclusive. QUICK EXPLANATIONLet 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! EXPLANATIONLet 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][i1] 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 18 Jul '13, 21:00

Hello, Very good editorial and it exploited some nice properties of the Sive of Erathostenes I wasn't aware of at all :) 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 :) Best regards, Bruno answered 18 Jul '13, 21:40

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 k^{th} list falls between A and B. Here is the link to my AC solution: http://www.codechef.com/viewplaintext/2326735 answered 23 Jul '13, 10:45

I used Segment Trees to solve this problem.I have just maintained five segment trees for each k :) answered 23 Jul '13, 12:08

Someone Please explain the memoization part done using table[][]. answered 20 Sep '15, 18:40

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 nonprime! Shouldn't prime[j]=No be done instead of prime[i*j] ? answered 17 Oct '16, 22:17

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 answered 09 Mar '17, 04:32

You'd had got timeout had the sieve function been inside the while loop in main function :p What you did was that you created the sieve first, precomputed your answer and then simply returned it after taking inputs in while loop. Precomputation 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' ) answered 09 Mar '17, 09:24

You'd had got timeout had the sieve function been inside the while loop in main function :p What you did was that you created the sieve first, precomputed your answer and then simply returned it after taking inputs in while loop. Precomputation 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' ) answered 09 Mar '17, 09:24
