Print the nearest prime number formed by adding prime numbers to N

0 0 9 minutes read

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 not
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
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
int 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 approach
 
import 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 not
def 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 number
def 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 Code
N = 8
 
# function call
result = 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 not
function 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 number
function makePrime(n) {
let sum = n;
// to check every number prime or not
for(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 Code
let N = 8;
 
// function call
let result = makePrime(N);
console.log(result);

Output

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 sieve
void 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 sieve
static 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 sieve
def 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 = 8
print(printNearest(N))

C#

// C# program to print the 
// nearest prime number by
// sequentially adding the
// prime numbers
using System;
using System.Collections.Generic;
     
class GFG 
{
 
// Function to store prime
// numbers using prime sieve
static 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 sieve
function 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

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 zambiatek!