 Practice

Easy

# PREREQUISITES:

Maths, Number theory

# PROBLEM:

We have to find N numbers such that GCD of all possible pairs of N numbers must be N, and minimize the sum of N numbers.

# EXPLANATION:

This problem can be solved by finding a set of N numbers such that the GCD of all possible pairs equals to 1 and then multiply the set of N numbers by N, so we can find N numbers such that their GCD equals to N

We can have many set of N numbers such that the GCD of all possible pairs equals to 1, but here we also have to satisfy the above condition ( i.e. minimize sum of N numbers). So, for this, we need to use 1 and first N-1 prime numbers . Therefore, we get a set of N numbers such that the GCD of all possible pairs equals to 1.

Finally, multiply the set of N numbers by N to get the required N numbers.

# SOLUTIONS:

Setter’s Solution
``````#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long int ll;

typedef vector<ll> vi;

vector<bool> prime;

void sieve()

{

prime.resize(10000001,1);

prime=0;

for(ll i=2;i<=10000000;i++)

if(prime[i])

for(ll j=i*i;j<=10000000;j+=i)

prime[j]=0;

}

int main()

{

fast;

ll n,cnt=0;

cin>>n;

sieve();

for(int i=1;cnt<n;i++)

{

if(prime[i])

{

cout<<n*i<<" ";

cnt++;

}

}

cout<<endl;

}
``````