You are not logged in. Please login at www.codechef.com to post your questions!

×

KPRIME - Editorial

14
10

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.

This question is marked "community wiki".

asked 18 Jul '13, 21:00

gamabunta's gravatar image

1★gamabunta
2.3k128183169
accept rate: 14%

edited 22 Jul '13, 14:21


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

link

answered 18 Jul '13, 21:40

kuruma's gravatar image

2★kuruma
17.5k72143208
accept rate: 8%

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

link

answered 23 Jul '13, 10:45

tijoforyou's gravatar image

3★tijoforyou
4.2k52364
accept rate: 15%

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

link

answered 24 Jul '13, 08:30

vikrant1433's gravatar image

3★vikrant1433
227369
accept rate: 0%

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

(01 Aug '13, 16:24) prashkr2★

actually it should be 1

(16 Dec '13, 23:39) shreyasiitr1★

In this case,it should be 1.

(03 Jan '14, 17:32) shubham262★

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

link

answered 23 Jul '13, 12:08

sandeepandey's gravatar image

2★sandeepandey
172
accept rate: 0%

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

link

answered 20 Sep '15, 18:40

nirmit_goyal's gravatar image

4★nirmit_goyal
32
accept rate: 0%

edited 20 Sep '15, 18:53

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] ?

link

answered 17 Oct '16, 22:17

Alexi%40Code99's gravatar image

2★Alexi@Code99
1
accept rate: 0%

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

link

answered 09 Mar, 04:32

akulgoel96's gravatar image

3★akulgoel96
1086
accept rate: 12%

@akulgoel

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. 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' )

link

answered 09 Mar, 09:24

vijju123's gravatar image

4★vijju123 ♦
11.3k1316
accept rate: 18%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×801
×213
×96
×19

question asked: 18 Jul '13, 21:00

question was seen: 7,112 times

last updated: 09 Mar, 09:24