Given a number N. The task is to print the nearest prime if the number is not prime by making it prime by adding prime numbers sequentially from 2.
Examples:
Input: N = 8
Output: 13
8 is not prime, so add the first prime to it to get 10
10 is not prime, hence add the second prime, i.e., 3 to get 13 which is prime.
Input: N = 45
Output: 47
Naive Approach : In this approach we add every prime number to given number N until we find the desired output.
- First run the loop from 2 to N*N and find a prime number.
- Then add that prime number to variable sum and check then the new sum formed is prime or not.
- If it is a Prime Number then return sum and if not then find another prime number and perform the same task again until sum become a prime number.
Implementation :
C++
// C++ code for the naive approach#include <bits/stdc++.h>using namespace std;// function to check if a number is prime or notbool isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= n/2; i++) { if (n % i == 0) { return false; } } return true;}// function to add all prime numbers to a given number until it becomes a prime numberint makePrime(int n) { int sum = n; // to check every number prime or not for(int i=2 ;i< n*n ;i++){ // the number is number then add it to sum if(isPrime(i)){ sum+=i; // check new sum formed is prime or not if(isPrime(sum)){ // sum is prime then return ans return sum; } } } return -1;}// Driver Codeint main() { int N = 8; // function call int result = makePrime(N); cout << result << endl; return 0;}// this code is contributed by bhardwajji |
Java
// Java code for the naive approachimport java.util.*;public class Main { // function to check if a number is prime or not static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= n / 2; i++) { if (n % i == 0) { return false; } } return true; } // function to add all prime numbers to a given number // until it becomes a prime number static int makePrime(int n) { int sum = n; // to check every number prime or not for (int i = 2; i < n * n; i++) { // the number is number then add it to sum if (isPrime(i)) { sum += i; // check new sum formed is prime or not if (isPrime(sum)) { // sum is prime then return ans return sum; } } } return -1; } // Driver Code public static void main(String[] args) { int N = 8; // function call int result = makePrime(N); System.out.println(result); }}// This code is contributed by sarojmcy2e |
Python3
# function to check if a number is prime or notdef isPrime(n): if n <= 1: return False for i in range(2, int(n/2) + 1): if n % i == 0: return False return True# function to add all prime numbers to a given number until it becomes a prime numberdef makePrime(n): sum = n # to check every number prime or not for i in range(2, n*n): # the number is number then add it to sum if isPrime(i): sum += i # check new sum formed is prime or not if isPrime(sum): # sum is prime then return ans return sum return -1# Driver CodeN = 8# function callresult = makePrime(N)print(result) |
C#
using System;class Program { // function to check if a number is prime or not static 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; } // function to add all prime numbers to a given number // until it becomes a prime number static int MakePrime(int n) { int sum = n; // to check every number prime or not for (int i = 2; i < n * n; i++) { // the number is prime then add it to sum if (IsPrime(i)) { sum += i; // check new sum formed is prime or not if (IsPrime(sum)) { // sum is prime then return ans return sum; } } } return -1; } static void Main(string[] args) { int N = 8; // function call int result = MakePrime(N); Console.WriteLine(result); }} |
Javascript
// JavaScript code for the naive approach// function to check if a number is prime or notfunction isPrime(n) {if (n <= 1) {return false;}for (let i = 2; i <= n/2; i++) {if (n % i == 0) {return false;}}return true;}// function to add all prime numbers to a given number until it becomes a prime numberfunction makePrime(n) {let sum = n;// to check every number prime or notfor(let i=2 ;i< n*n ;i++){ // the number is number then add it to sum if(isPrime(i)){ sum+=i; // check new sum formed is prime or not if(isPrime(sum)){ // sum is prime then return ans return sum; } }}return -1;}// Driver Codelet N = 8;// function calllet result = makePrime(N);console.log(result); |
Output
13
Time Complexity: O((N * N) * N) // run loop from 2 to N*N to find the prime number. and N to check every number is prime or not.
Auxiliary Space: O(1) // no extra space used
Approach Using Sieve of Eratosthenes, mark the prime index by 1 in isprime[] list and store all the prime numbers in a list prime[]. Keep adding prime numbers sequentially to N, till it becomes prime.
Below is the implementation of the above approach:
C++
// C++ program to print the // nearest prime number by// sequentially adding the// prime numbers #include<bits/stdc++.h>using namespace std;// Function to store prime// numbers using prime sievevoid prime_sieve(int MAX, vector<int> &isprime, vector<int> &prime){ // iterate for all // the numbers int i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime // to the list prime.push_back(i); // Update all multiples of p for (int j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; }} // Function to print // the nearest prime int printNearest(int N){ int MAX = 1e6; // store all the // index with 1 vector<int> isprime(MAX, 1); // 0 and 1 are not prime isprime[0] = isprime[1] = 0; // list to store // prime numbers vector<int> prime; // variable to // add primes int i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (!isprime[N]) { N += prime[i]; i += 1; } // return the // nearest prime return N ;}// Driver Code int main(){ int N = 8; printf("%d", printNearest(N)); return 0;}// This code is contributed// by Harshit Saini |
Java
// Java program to print the // nearest prime number by// sequentially adding the// prime numbers import java.util.*;class GFG {// Function to store prime// numbers using prime sievestatic void prime_sieve(int MAX, int []isprime, Vector<Integer> prime){ // iterate for all // the numbers int i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime // to the list prime.add(i); // Update all multiples of p for (int j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; }} // Function to print // the nearest prime static int printNearest(int N){ int MAX = (int) 1e6; // store all the // index with 1 except 0,1 index int [] isprime = new int[MAX]; for(int i = 2; i < MAX; i++) isprime[i] = 1; // list to store // prime numbers Vector<Integer> prime = new Vector<Integer>(); // variable to add primes int i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (isprime[N] == 0) { N += prime.get(i); i += 1; } // return the // nearest prime return N ;}// Driver Code public static void main(String[] args){ int N = 8; System.out.printf("%d", printNearest(N));}} // This code is contributed by Rajput-Ji |
Python3
# Python3 program to print the nearest prime # number by sequentially adding the prime numbers # Function to store prime numbers using prime sievedef prime_sieve(MAX, isprime, prime): # iterate for all the numbers i = 2 while (i * i <= MAX): # If prime[p] is not changed, # then it is a prime if (isprime[i] == 1): # append the prime to the list prime.append(i) # Update all multiples of p for j in range(i * 2, MAX, i): isprime[j] = 0 i += 1 # Function to print the nearest prime def printNearest(N): MAX = 10**6 # store all the index with 1 isprime = [1] * MAX # 0 and 1 are not prime isprime[0] = isprime[1] = 0 # list to store prime numbers prime = [] # variable to add primes i = 0 # call the sieve function prime_sieve(MAX, isprime, prime) # Keep on adding prime numbers # till the nearest prime number # is achieved while not isprime[N]: N += prime[i] i += 1 # return the nearest prime return N # Driver Code N = 8print(printNearest(N)) |
C#
// C# program to print the // nearest prime number by// sequentially adding the// prime numbersusing System;using System.Collections.Generic; class GFG {// Function to store prime// numbers using prime sievestatic void prime_sieve(int MAX, int []isprime, List<int> prime){ // iterate for all the numbers int i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime to the list prime.Add(i); // Update all multiples of p for (int j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; }} // Function to print // the nearest prime static int printNearest(int N){ int MAX = (int) 1e6; int i = 0; // store all the // index with 1 except 0,1 index int [] isprime = new int[MAX]; for(i = 2; i < MAX; i++) isprime[i] = 1; // list to store // prime numbers List<int> prime = new List<int>(); // variable to add primes i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (isprime[N] == 0) { N += prime[i]; i += 1; } // return the // nearest prime return N;}// Driver Code public static void Main(String[] args){ int N = 8; Console.Write("{0}", printNearest(N));}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to print the // nearest prime number by// sequentially adding the// prime numbers // Function to store prime// numbers using prime sievefunction prime_sieve(MAX, isprime, prime){ // iterate for all // the numbers var i = 2; while (i * i <= MAX) { // If prime[p] is not changed, // then it is a prime if (isprime[i] == 1) { // append the prime // to the list prime.push(i); // Update all multiples of p for (var j = i * 2; j < MAX; j += i) { isprime[j] = 0; } } i += 1; }} // Function to print // the nearest prime function printNearest(N){ var MAX = 1e6; // store all the // index with 1 var isprime = Array(MAX).fill(1); // 0 and 1 are not prime isprime[0] = isprime[1] = 0; // list to store // prime numbers var prime = []; // variable to // add primes var i = 0; // call the sieve function prime_sieve(MAX, isprime, prime); // Keep on adding prime // numbers till the nearest // prime number is achieved while (!isprime[N]) { N += prime[i]; i += 1; } // return the // nearest prime return N ;}// Driver Code var N = 8;document.write( printNearest(N));// This code is contributed by rrrtnx.</script> |
Output
13
Time Complexity: O(N * log(logN))
Auxiliary Space: O(N)
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!
