Given an integer N, the task is to find the minimum number K to be added to N such that N + K becomes a prime number.
Examples:
Input: N = 10
Output: 1
Explanation:
1 is the minimum number to be added to N such that 10 + 1 = 11 is a prime number
Input: N = 20
Output: 3
Approach: The idea is to check whether the number is a prime or not by incrementing the value to be added K by 1 in each iteration. Therefore, the following steps can be followed to compute the answer:
- Initially, check whether the given number is prime or not. If it is, then the value to be added(K) is 0.
- Now, in every iteration, increment the value of N by 1 and check if the number is prime or not. Let the first value at which N becomes a prime is M. Then, the minimum value that needs to be added to make N prime is M – N.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum// number to be added to N to// make it a prime number#include <bits/stdc++.h>using namespace std;// Function to check if a given number// is a prime or notbool isPrime(int n){ // Base cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; // For all the remaining numbers, check if // any number is a factor if the number // or not for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; // If none of the above numbers are the // factors for the number, then the // given number is prime return true;}// Function to return the smallest// number to be added to make a// number primeint findSmallest(int N){ // Base case if (N == 0) return 2; if (N == 1) return 1; int prime = N, counter = 0; bool found = false; // Loop continuously until isPrime returns // true for a number greater than n while (!found) { if (isPrime(prime)) found = true; else { // If the number is not a prime, then // increment the number by 1 and the // counter which stores the number // to be added prime++; counter++; } } return counter;}// Driver codeint main(){ int N = 10; cout << findSmallest(N); return 0;} |
Java
// Java program to find the minimum// number to be added to N to// make it a prime numberimport java.util.*;class GFG{ // Function to check if a given number// is a prime or notstatic boolean isPrime(int n){ // Base cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; // For all the remaining numbers, check if // any number is a factor if the number // or not for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; // If none of the above numbers are the // factors for the number, then the // given number is prime return true;} // Function to return the smallest// number to be added to make a// number primestatic int findSmallest(int N){ // Base case if (N == 0) return 2; if (N == 1) return 1; int prime = N, counter = 0; boolean found = false; // Loop continuously until isPrime returns // true for a number greater than n while (!found) { if (isPrime(prime)) found = true; else { // If the number is not a prime, then // increment the number by 1 and the // counter which stores the number // to be added prime++; counter++; } } return counter;} // Driver codepublic static void main(String[] args){ int N = 10; System.out.print(findSmallest(N));}}// This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to find the minimum# number to be added to N to# make it a prime number# Function to check if a given number# is a prime or notdef isPrime(n): # Base cases if (n <= 1): return False if (n <= 3): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False # For all the remaining numbers, check if # any number is a factor if the number # or not i = 5 while (i * i <= n ): if (n % i == 0 or n % (i + 2) == 0): return False i += 6 # If none of the above numbers are the # factors for the number, then the # given number is prime return True # Function to return the smallest# number to be added to make a# number primedef findSmallest(N): # Base case if (N == 0): return 2 if (N == 1): return 1 prime , counter = N, 0 found = False # Loop continuously until isPrime returns # true for a number greater than n while (not found): if (isPrime(prime)): found = True else : # If the number is not a prime, then # increment the number by 1 and the # counter which stores the number # to be added prime += 1 counter += 1 return counter # Driver codeif __name__ == "__main__": N = 10 print(findSmallest(N)) # This code is contributed by chitranayal |
C#
// C# program to find the minimum// number to be added to N to// make it a prime numberusing System;class GFG{// Function to check if a given number// is a prime or notstatic bool isPrime(int n){ // Base cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; // For all the remaining numbers, check if // any number is a factor if the number // or not for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; // If none of the above numbers are the // factors for the number, then the // given number is prime return true;}// Function to return the smallest// number to be added to make a// number primestatic int findSmallest(int N){ // Base case if (N == 0) return 2; if (N == 1) return 1; int prime = N, counter = 0; bool found = false; // Loop continuously until isPrime returns // true for a number greater than n while (!found) { if (isPrime(prime)) found = true; else { // If the number is not a prime, then // increment the number by 1 and the // counter which stores the number // to be added prime++; counter++; } } return counter;}// Driver codepublic static void Main(){ int N = 10; Console.Write(findSmallest(N));}}// This code is contributed by AbhiThakur |
Javascript
<script>// Javascript program to find the minimum// number to be added to N to// make it a prime number// Function to check if a given number// is a prime or notfunction isPrime(n){ // Base cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; // For all the remaining numbers, check if // any number is a factor if the number // or not for (var i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; // If none of the above numbers are the // factors for the number, then the // given number is prime return true;}// Function to return the smallest// number to be added to make a// number primefunction findSmallest(N){ // Base case if (N == 0) return 2; if (N == 1) return 1; var prime = N, counter = 0; var found = false; // Loop continuously until isPrime returns // true for a number greater than n while (!found) { if (isPrime(prime)) found = true; else { // If the number is not a prime, then // increment the number by 1 and the // counter which stores the number // to be added prime++; counter++; } } return counter;}// Driver codevar N = 10;document.write( findSmallest(N));// This code is contributed by noob2000.</script> |
Output:
1
Time Complexity: O(k*sqrt(k)) (where k = M-N, N = input, M = first prime no.)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/find-the-minimum-number-to-be-added-to-n-to-make-it-a-prime-number/ […]