### guacamolesyrup's blog

By guacamolesyrup, history, 4 years ago, 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;

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;
}
}
}
} Comments (10)
 » Just look for the smallest prime such that it is not the factor of any of the numbers?
•  » » - #include 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 vectorprime; bool isprime; 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
•  » » » instead of trying to find the prime factor by factoring the numbers, you can find the prime factor of a number in log after some preprocessing. Here's a link that might help.
 » Auto comment: topic has been updated by guacamolesyrup (previous revision, new revision, compare).
 » 5 months ago, # | ← Rev. 3 →   This is my AC solution. Hope it helps. spf[x] is the smallest prime factor of a number x. The idea here is to mark all the prime factors of all numbers efficiently and then print the smallest unmarked prime. bool prime[N+5]; vector primesVec; void SieveOfEratosthenes(ll n) { memset(prime, true, sizeof(prime)); prime = prime = false; for(ll p=2; p*p<=n; p++){ if (prime[p] == true){ for(ll i=p*p;i<=n;i+=p) prime[i] = false; } } for(ll p=2; p<=n; p++){ if (prime[p]) { primesVec.push_back(p); } } } ll spf[N]; void SPF() { spf = 1; // marking smallest prime factor for every number to be itself. for (ll i = 2; i < N; i++) spf[i] = i; // separately marking spf for every even number as 2 for (ll i=4; i> n; f(i, n) { cin >> x; getFactorization(x); } for(int p: primesVec) { if(check[p] == 0) { cout << p << endl; return; } } } 
•  » » Thanks, He was waiting for the solution for the past 3 years.
•  » » » Maybe others who have started CP can benefit from this. XD
•  » » » See I helped because I too visit old blogs and sometimes people do lord's job by posting valuable stuff about the problem which I like the most about codeforces blogs. The blog is not just for a single person rather its for the whole codeforces community.
•  » » But it seems like the poster has been away from CF for nearly 2 years. :(
•  » » » Yes, and that does not matter at all. There may be other people looking for the solution.Obligatory XKCD: 