# CFACTOR - Editorial

Author: Srinjoy Ray
Tester: Ankur Kayal
Editorialist: Srinjoy Ray

EASY-MEDIUM

Math

# PROBLEM:

N integers are given. We will have to find the smallest integer greater than 1 that gives gcd equal to 1 with each of the N integers.

# QUICK EXPLANATION:

We can precompute all the primes and mark all the prime factors of the N integers. The smallest prime not marked is our answer.

# EXPLANATION:

The first observation is that the final answer must be a prime number.

Suppose a composite number C gives gcd equal to 1 with each of the N integers, then each of the prime factors of C will also give gcd equal to 1 with each of the N integers . So the smallest such number must be a prime.

Our final answer can never be greater than the prime number just greater than 10^6, i.e., 10^6+3. So, we can precompute all the primes till of 2×10^6 (Link). Also we can precompute the smallest prime factor of all the numbers till 10^6 (Link).

For each of the N integers we can mark all the prime factors of that number. Then we can traverse and find the smallest prime number that have not been marked.

Time Complexity : O(Nlog A) per testcase and O(NloglogN) for sieve.

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

const int N=2e6;

int spf[N],present[N];
bool prime[N + 1];
vector<int> v_prime;

void sieve()
{
memset(prime, true, sizeof(prime));

spf[1] = 1;
prime[0]=false; prime[1]=false;

for(int i=2; i<N; i++){
spf[i] = i;
}

for (int p = 2; p * p <= N; p++){
if (prime[p] == true){
for(int i = p * p; i <= N; i += p){
prime[i] = false;
spf[i] = p;
}
}
}

for(int p=2;p<=N;p++){
if(prime[p]){
v_prime.push_back(p);
}
}

}

void solve(){
int i,j;
int n;
cin>>n;
int a[n],temp,ans;
set<int> present_primes;
for(i=0;i<n;i++){
cin>>a[i];
}

for(i=0;i<n;i++){

while(spf[a[i]] != a[i]){
temp = spf[a[i]];
present[temp]++;
present_primes.insert(temp);
while(a[i]%temp == 0){
a[i]/=temp;
}
}

present[a[i]]++;
present_primes.insert(a[i]);

}

for(i=0;i<v_prime.size();i++){
if(present[v_prime[i]]==0){
ans = v_prime[i];
break;
}
}
for(auto it : present_primes){
present[it] = 0;
}

cout<<ans<<'\n';
}

int main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
cin>>t;
sieve();
while(t--){
solve();
}

}

``````
Tester's Solution
``````smallest_factor = []
prime = []
primes = []

def sieve(maximum):
global smallest_factor
global prime
global primes

maximum = max(maximum, 1)
smallest_factor = [0 for _ in range(maximum + 1)]
prime = [True for _ in range(maximum + 1)]
prime[0] = prime[1] = False

for p in range(2, maximum + 1):
if prime[p]:
smallest_factor[p] = p
primes.append(p)

for i in range(p * p, maximum + 1, p):
if prime[i]:
prime[i] = False
smallest_factor[i] = p

def prime_factorize(n):
global smallest_factor
result = []

while n != 1:
p = smallest_factor[n]
exponent = 0

while n % p == 0:
n //= p
exponent += 1

result.append([p, exponent])

return result

def solve():
N = int(input())
A = list(map(int, input().split()))

unique = set()

for i in A:
for j in prime_factorize(i):

for i in primes:
if i not in unique:
print(i)
return

def main():
sieve(10**6+7)
t = int(input())
for _ in range(t):
solve()

if __name__ == "__main__":
import bisect
import math
import itertools
from sys import stdout

############  Sorted Containers  ######################
import heapq
from queue import PriorityQueue
from collections import OrderedDict

############ Tree Problems ( Use Python 3) ###########
sys.setrecursionlimit(2 ** 32 // 2 - 1)