PROBLEM LINK:
DIFFICULTY:
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]=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;
}