Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Smallest prime giving the rest Ok when divided by any Array component

[ad_1]

Given an array of integers arr[] of dimension N and an integer Ok, the duty is to search out the smallest prime such that it offers the rest Ok when it’s divided by any of the weather of the array.

Word: The prime quantity must be within the vary [1, 106]

Examples:

Enter: arr[]= {3, 4, 5}, Ok = 1
Output: 61
Rationalization: The smallest prime that satisfies the situation is 61. 
61percent3 = 1, 61percent4 = 1 and 61percent5 =1.

Enter: arr[] = {2, 4, 5}, Ok = 3
Output: -1
Rationalization: The output shouldn’t be doable as a result of 
no quantity can have the rest 3 when divided by 2. 

Enter: arr[] = {10, 4, 5}, Ok = 3
Output: 23
Rationalization: The smallest prime that satisfies the situation is 23. 
23percent10 = 3, 23percent4 = 3 and 23percent5 = 3

 

Method: The thought to unravel the issue is talked about beneath:

The LCM of numbers is the smallest nummber divisble by all the opposite numbers. So discover the LCM of the array and examine for every a number of of the LCM whether or not LCM + Ok is prime or to not get the smallest prime which provides the rest as Ok.
If any component of the array is smaller than Ok then resolution isn’t doable. As a result of no quantity can have a reaminder increased than itself when dividing a quantity.

Comply with the beneath steps for the above:

  • First, discover the lcm of all the weather of the array(say lcm).
  • Iterate for every a number of of lcm that are lower than or equal to 106:
    • Verify whether or not (lcm + Ok) is prime or not for every a number of of lcm
    • If the situation holds true, return the sum of Ok  and the present a number of of lcm because the smallest_prime.
  • If no prime quantity is discovered, return -1.

Under is the implementation of the above strategy: 

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

lengthy lengthy gcd(lengthy lengthy int a,

              lengthy lengthy int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b);

}

bool checkPrime(lengthy lengthy n)

{

    lengthy lengthy ub = sqrt(n);

    for (lengthy lengthy i = 2; i <= ub; i++) {

        if (n % i == 0) {

            return false;

        }

    }

    return true;

}

  

lengthy lengthy smallestPrime(vector<int> arr,

                        int q)

{

  

    

    lengthy lengthy lcm = arr[0];

    for (int i : arr) {

        lcm = (lcm * i) / (gcd(i, lcm));

    }

  

    

    

    for (auto i : arr) {

        if (i < q)

            return -1;

    }

    

    

    for (lengthy lengthy i = lcm; i <= 1e9;

         i += lcm) {

        if (checkPrime(i + q)) {

            return i + q;

        }

    }

  

    

    

    

    return -1;

}

  

int major()

{

  

    vector<int> arr = { 2, 5, 4 };

    int q = 3;

    cout << smallestPrime(arr, q);

    return 0;

}

Time Complexity: O(N * logD + (M/lcm)*sqrt(M)) the place D is max of array, M is higher doable restrict of prime, lcm is LCM of all array components
Auxiliary Area: O(1)

[ad_2]

Leave a Reply