GCD

Revision en2, by guacamolesyrup, 2017-08-15 12:43:45

Sabbir and GCDs I was trying this problem but somehow i am getting WA after 10th testcase. Can anyone give me some hints how to solve it?Thanks in advance.I have updated my solution now it is showing WA again.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define MAX 100009
#define MOD 1000000007
#define fast ios::sync_with_stdio(false);
#define INF 1000000000000000LL
#define INM -INF
#define pi 3.14159265358979323846264338327950

vector<int>prime;
bool isprime[1000011];

void sieve(){
for(int i=2;i<=sqrt(1000010);i++){
if(!isprime[i]){
for(int j=i+i;j<=1000010;j+=i)
isprime[j]=1;
}
}
prime.pb(2);
for(int i=3;i<=1000010;i+=2){
if(!isprime[i])
prime.pb(i);
}
}
int main(){
fast
int t;
sieve();
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
set<int>S;
for(int i=0;i<n;i++){
for(int j=0;j<prime.size()&& prime[j]*prime[j]<=a[i];j++){
while(a[i]%prime[j]==0){
S.insert(prime[j]);
a[i]/=prime[j];
}
}
if(a[i]>1){
S.insert(a[i]);
}
}
for(int i=0;i<prime.size();i++){
if(S.find(prime[i])==S.end()){
printf("%d\n",prime[i]);
break;
}
}
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en2 guacamolesyrup 2017-08-15 12:43:45 1222
en1 guacamolesyrup 2017-08-15 11:21:11 196 Initial revision (published)