Project Euler #47: Distinct primes factors

  • + 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';
        }
    }