# 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

62376354100120720125

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.