KPRIME - Editorial

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.

19 Likes

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

6 Likes

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

4 Likes

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

1 Like

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

7 Likes

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

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

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

@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’ )

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

actually it should be 1

In this case,it should be 1.

   Can anyone help me with my code ? 

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
ll p[100011]={0};
ll binasea(ll arr[],ll n,ll k)
{
    ll l = 0, r = n-1;
    ll m;
    while (l <= r)
    {
        m = (r + l)/2;
        if (arr[m] == k)
        {
            return m;
        }
        else if (arr[m] > k)
            r = m-1;
        else
            l = m + 1;
    }
    return -1;
}
void pm()
{   ll j;
    for(ll i=2;i<sqrt(100001);i++)
    {
        if(p[i]==0){
        for( j=2*i;j<100001;j+=i)
        {
            p[j]++;
        }}
    }
}
int main()
{
    ll t,n=0,i,j,k=0;
    pm();
    vector<ll> a,b,c,d,e;
    ll a1,b1;
    for(int i=2;i<100001;i++)
    {
        if(p[i]==0)p[i]=1;
        if(p[i]==1)a.pb(i);
        if(p[i]==2)b.pb(i);
        if(p[i]==3)c.pb(i);
        if(p[i]==4)d.pb(i);
        if(p[i]==5)e.pb(i);
    }
    cin>>t;
    //for(i=0;i<b.size();i++)
    //cout<<b[i]<<" ";
    //  cout<<i<<" "<<p[i]<<endl;
    while(t--)
    {
        cin>>a1>>b1>>k;
        n=0;
        switch (k)
        {
            case 1:n=lower_bound(a.begin(),a.end(),b1)-lower_bound(a.begin(),a.end(),a1)+1;
                    if(binasea(&a[0],a.size(),b1)==-1)n--;break;
            case 2:n=lower_bound(b.begin(),b.end(),b1)-lower_bound(b.begin(),b.end(),a1)+1;
                    if(binasea(&b[0],b.size(),b1)==-1)n--;break;
            case 3:n=lower_bound(c.begin(),c.end(),b1)-lower_bound(c.begin(),c.end(),a1)+1;
                    if(binasea(&c[0],c.size(),b1)==-1)n--;break;
            case 4:n=lower_bound(d.begin(),d.end(),b1)-lower_bound(d.begin(),d.end(),a1)+1;
                    if(binasea(&d[0],d.size(),b1)==-1)n--;break;
            case 5:n=lower_bound(e.begin(),e.end(),b1)-lower_bound(e.begin(),e.end(),a1)+1;
                    if(binasea(&e[0],e.size(),b1)==-1)n--;break;
        }
        //if(p[a1]==k)n++;
        //if(p[b1]==k)n++;
        cout<<n<<"\n";
    }
return 0;
}

Hello, your approach seems nice. Can I get the code to your approach?

I wrote a code using the same logic. But codechef platform is so shitty.
In my initial code, I took input of a,b,k in main function only and it showed “Runtime Error(SIGSEGV)”.
But when I used a auxiliary function to take input, like -
while(test–)
{
solve();
}
Then it passed perfectly.
I dont know what the problem is with codechef, this thing wasted my 3 hours.

I’m not able to understand why we need memoization. Can’t we simply do this? This solution isn’t passing all the test cases. Plz can someone suggest to me some test cases where this code won’t get accepted

public static void main (String[] args) throws java.lang.Exception {
	    long[] sieve = sieveOfEratosthenesModification(100001);
	    
		FastReader s = new FastReader();
        int T = s.nextInt();

        while (T-- > 0) {
            int A = s.nextInt();
            int B = s.nextInt();
            int K = s.nextInt();

            long ans = 0;

            for (int i = A; i <= B; i++) {
                if(sieve[i] == 0){
                    sieve[i]++;
                }
                
                if(sieve[i] == K){
                    ans++;
                }
            }

            System.out.println(ans);
        }
	}
	
	private static long[] sieveOfEratosthenesModification(int N) {
        long[] arr = new long[(int) N + 1];

        int i = 0;
        
        for (i = 2; i * i <= N; i++) {
            if (arr[i] == 0) {
                // arr[i] = 1;

                for (int j = 2; i * j <= N; j++) {
                    arr[i * j]++;
                }
            }
        }

        return arr;
    }

Hey @pravin45 :wave: ,
You have implemented wrong Sieve of Eratosthenes also I didn’t you over the condition if(sieve[I]==0) sieve[I]++ but I have written and modified your code in C++ please check it out.

#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
    static char buffer[64];
    int index = 0;
    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
    if (value < 0)
        os << '-';
    else if (T == 0)
        return os << '0';
    for (; T > 0; ++index) {
        buffer[index] = static_cast<char>('0' + (T % 10));
        T /= 10;
    }
    while (index > 0)
        os << buffer[--index];
    return os;
}
istream& operator >> (istream& is, __int128& T) {
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0; int mul = 1;
    if (buffer[index] == '-')
        ++index, mul *= -1;
    for (; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;
    return is;
}
#endif
vector<int> sieveOfEratosthenesModification(int N)
{
     vector<int> arr(N + 1,0);
        int i = 0;
        arr[1]=1;
        for (i = 2; i <= N; i++) {
            if (arr[i] == 0) {
                arr[i]++;
                for (int j = i+i; j <= N; j+=i) {
                    arr[j]++;
                }
            }
        }

        return arr;
}
int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    auto sieve = sieveOfEratosthenesModification(100001);
    cin.tie(NULL);
    int T;
    cin>>T;

        while (T-- > 0) {
            int A,B,K ;
            cin>>A>>B>>K;
            long ans = 0;
            for (int i = A; i <= B; i++) {
                if(sieve[i] == K){
                    ans++;
                }
            }
            cout<<ans<<"\n";
        }
    return 0;
}