# 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;
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. Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown