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 followsmahmut_eren72
's hint. However, I though it was a bit too complicated, so I simplified it in my Python3 code below, addressingdaragunshot
's concern.Note that my
A[x]
is the exact number of prime factors ofx
and that my Eratosthenes code below doesn't divide or multiply, which are computationally expensive for largeN
. If one wanted the distinct prime factors themselves, one can modify the code below to initialze eachA[x]
to the empty list[]
and then doA[n].append(p)
instead ofA[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