We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #47: Distinct primes factors
  4. Discussions

Project Euler #47: Distinct primes factors

Problem
Submissions
Leaderboard
Discussions

Sort 27 Discussions, By:

recency

Please Login in order to post a comment

  • leduckhai
    2 years ago+ 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|
    Permalink
  • s_mostafa_a
    2 years ago+ 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|
    Permalink
  • s_mostafa_a
    2 years ago+ 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|
    Permalink
  • happy_coder_
    3 years ago+ 0 comments

    you can find my java solution here

    0|
    Permalink
  • qayum_khan_usa
    3 years ago+ 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
    
    1|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy