# Project Euler #47: Distinct primes factors

# Project Euler #47: Distinct primes factors

+ 0 comments After a day of googling, I had realized this:

If you use common codes to find

**prime factors**like here: https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ , you cannot pass all test cases coz its time complexity =**O(n^0.5)**(I though it was the fastest algorithm ever but I was wrong)If you use a more efficient algorithm like here: https://www.geeksforgeeks.org/efficient-program-print-number-factors-n-numbers/?ref=rp , you can pass coz it's only

**O(logn)**

+ 0 comments C++ Solution :

#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() #define debug(x) cout << #x << " = " << x << endl typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; inline ll Mod(ll x, ll mod) { return x % mod >= 0 ? x % mod : x % mod + mod; } int is_prime[2000 * 1000 + 1] = {0}; void sieve(int N) { for (int i = 2; i <= N; ++i) { if (!is_prime[i]) { for (int j = i; j <= N; j += i) is_prime[j]++; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); sieve(2000 * 1000); int n, k; cin >> n >> k; for (int i = 2; i <= n; i++) { bool flag = 0; for (int j = 0; j < k; j++) { if (is_prime[i + j] != k) { flag = 1; break; } } if (!flag) cout << i << '\n'; } }

+ 0 comments First find the number of different prime factors of all numbers in range [2,2000000] using an algorithm similar to sieve of eratosten. Then for each test case, iterate over all numbers from 2 to N and check is there is an answer or not.

+ 0 comments you can find my java solution here

+ 0 comments I appreciate

`dingma129`

's code, which follows`mahmut_eren72`

's hint. However, I though it was a bit too complicated, so I simplified it in my**Python3**code below, addressing`daragunshot`

's concern.Note that my

`A[x]`

is the*exact*number of prime factors of`x`

and that my Eratosthenes code below doesn't divide or multiply, which are computationally expensive for large`N`

. If one wanted the*distinct prime factors themselves*, one can modify the code below to initialze each`A[x]`

to the empty list`[]`

and then do`A[n].append(p)`

instead of`A[n] += 1`

.Due to some hangup in HackerRank for me, I currently cannot add comments to existing threads, though this post belongs to the above-linked thread of

`dingma129`

.def distinct_sieve(N): A = [0] * (1+N) for p in range(2,1+N): if A[p] : continue for n in range(p,1+N,p) : A[n] += 1 return A

Sort 27 Discussions, By:

Please Login in order to post a comment