PROBLEM LINK:
Author: Srinjoy Ray
Tester: Ankur Kayal
Editorialist: Srinjoy Ray
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
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):
unique.add(j[0])
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 sys, threading
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)
threading.stack_size(1 << 27)
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()