Find distinct prime factors from 1 to n in O((n+q)logn) (for q Queries)

Problem: Find distinct prime factors of a number. You will be asked q times.

Naive approach: Find out distinct prime factors for each query. It’s inefficient for large number of queries. As each query may have worst case time complexity on O(n), for large number of quaries O(q*sqrt(n))

Better Approach: precalculate and store all the answers in time and space complexity of O(nlogn) and answer each query in O(logn).

The idea is very similer to Sieve of Eratosthenes, infact a modified version of it. (If you are new to Seive of Erathosthenes, please read it before proceed further.) For each prime number, we simply store it in all it’s multiple upto n.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll const prime_upto=1000005;
vector<vector<ll>> d_prime_factors(prime_upto + 1);
void distinct_prime_factors(ll n=prime_upto)
{
    for (ll p = 2; p<= n; p++)
        if (!(d_prime_factors[p].size()))//condition for p being prime, i.e. no prime factors smaller than itself
            for (ll i = p; i <= n; i += p)//concatenating this prime number to all it's multiple less than equal to n
                d_prime_factors[i].push_back(p);
}


int main(){
    ll q,n;
  //pre-computing all the answers
    distinct_prime_factors();
    cin>>q;
  
  //loop for q queries
    while(q--){
        cin>>n;
      //for each query itterating through the pre-computed answer
        for(auto ax:d_prime_factors[n])
            cout<<ax<<" ";//printing one by one
        cout<<endl;
    }
    return 0;
}

Sample Input

6
23
76354
100
120
720
125

Output

23
2 38177
2 5
2 3 5
2 3 5
5

Explaination

In 1st query, as 23 is a prime number so only prime factor is 23. In 4th query for n=120 120=2*2*2*3*5. Distinct prime factors are 2,3 and 5.

If you like our efforts, please let us know in the comment section below.

Share on Social Media
Mukuldeep Maiti

Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown

You may also like...

Leave a Reply