PRIMECONS Editorial

editorial
1

Problem Explanation

You are given an array of elements and you have to output a prime number P such that the remainder of P divided by every number in the array except the smallest number is the smallest number itself.

Approach

We calculate the LCM of all the elements except the smallest number Q. Since the remainder of LCM divided by all the numbers will be zero, we add Q to the LCM. Now we check if the result is prime or not. If it is prime it will be our answer. Otherwise, no answer will exist.

Code

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// Returns LCM of array elements
int findlcm(vector< int>arr, int n)
{
    // Initialize result
    int ans = arr[0];
    // ans contains LCM of arr[0], ..arr[i]
    // after i'th iteration,
    for (int i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));
    return ans;
}

bool isPrime(int n)
{
    if (n <= 1)
        return false;
 
    for (int i = 2; i <= n / 2; i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 

int main(){
    int n;
    cin>>n;
    vector< int>v;
    for(int i=0;i< n;i++){
        int t;
        cin>>t;
        v.push_back(t);
    }
    int a = *min_element(v.begin(), v.end());
   auto it = find(v.begin(), v.end(), a);
    if (it != v.end())
        v.erase(it);
    int res;
    res = findlcm(v, n-1);
    if(isPrime(res+a))
        cout<< res+a;
    else cout<<"None"<<endl;
}```