Additive Prime Number

0 0 6 minutes read

Given a number N, the task is to check if N is an Additive Prime Number or not. If N is an Additive Prime Number then print “Yes” else print “No”.

An Additive Prime Number is a prime number P such that the sum of digits of P is also a prime number.
For example, 23 is an Additive prime because 2 + 3 = 5 which is a prime number.

Examples:

Input: N = 23
Output: Yes
Explanation: Sum of digits of 23 = 2 + 3 = 5.

Input: N = 10
Output: No

Approach: The idea is to find the sum of digits of the number N and check if it is prime or not. If the sum is a prime number then print “Yes” else print “No”.

Algorithm:

Define a function named isPrime that takes an integer as input and returns true if it is a prime number, and false otherwise.
Check if the input number is less than or equal to 1. If yes, return false.
Use a for loop to iterate from 2 to the square root of the input number. If the input number is divisible by any number in this range, return false. Otherwise, return true.
Define a function named digit_sum that takes an integer as input and returns the sum of its digits.
Initialize a variable ans to 0.
Use a while loop to iterate as long as the input number is greater than 0.
Add the last digit of the input number to ans and remove the last digit from the input number.
Return ans.
Define a function named additive_prime that takes an integer as input and returns 1 if it is an additive prime, and 0 otherwise.
Check if the input number is a prime number using the isPrime function.
If the input number is a prime number, calculate the sum of its digits using the digit_sum function.
Check if the sum of digits is a prime number using the isPrime function.
If both the input number and its sum of digits are prime numbers, return 1. Otherwise, return 0.
In the main function:

a. Define an integer variable.

b. Call the additive_prime function with the integer variable as an argument.

c. If the function returns 1, print “Yes” to the console. Otherwise, print “No”.

End of the program.

Below is the implementation of the above approach:

C++

#include <iostream>
using namespace std;
 
// Function to check whether a number is prime or not.
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
  //suppose n=7 that is prime and its pair are (1,7)
  //so if a no. is prime then it can be check by numbers smaller than square root
  // of the n
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
// Function to find the sum of the digits of a number.
int digit_sum(int n)
{
    int ans = 0;
    while (n > 0) {
        ans += (n % 10);
        n /= 10;
    }
    return ans;
}
 
// Function to check whether a number is additive prime or
// not.
int additive_prime(int n)
{
    if (isPrime(n)) {
        int d_sum = digit_sum(n);
        if (isPrime(d_sum))
            return 1;
    }
    return 0;
}
 
// Driver Code
int main()
{
 
    int n = 23;
 
    // Function Call
    if (additive_prime(n))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Java

import java.util.*;
 
public class Gfg {
 
  // Function to check whether a number is prime or not.
  public static boolean isPrime(int n) 
  {
 
    // Corner cases
    if (n <= 1) {
      return false;
    }
 
    // Suppose n=7 that is prime and its pair are (1,7)
    // So if a no. is prime then it can be check by numbers smaller than square root
    // of the n
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
 
  // Function to find the sum of the digits of a number.
  public static int digit_sum(int n) {
    int ans = 0;
    while (n > 0) {
      ans += (n % 10);
      n /= 10;
    }
    return ans;
  }
 
  // Function to check whether a number is additive prime or not.
  public static int additive_prime(int n) {
    if (isPrime(n)) {
      int d_sum = digit_sum(n);
      if (isPrime(d_sum)) {
        return 1;
      }
    }
    return 0;
  }
 
  // Driver Code
  public static void main(String[] args) {
    int n = 23;
 
    // Function Call
    if (additive_prime(n) == 1) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

Python

# Python Equivalent 
 
# Function to check whether a number is prime or not.
def isPrime(n):
    # Corner cases
    if (n <= 1):
        return False
    #suppose n=7 that is prime and its pair are (1,7)
    #so if a no. is prime then it can be check by numbers smaller than square root
    # of the n
    for i in range(2, int(n**0.5) + 1):
        if (n % i == 0):
            return False
    return True
 
# Function to find the sum of the digits of a number.
def digit_sum(n):
    ans = 0
    while (n > 0):
        ans += (n % 10)
        n = int(n/10)
    return ans
 
# Function to check whether a number is additive prime or
# not.
def additive_prime(n):
    if (isPrime(n)):
        d_sum = digit_sum(n)
        if (isPrime(d_sum)):
            return 1
    return 0
 
# Driver Code
if __name__ == '__main__':
    n = 23
 
    # Function Call
    if (additive_prime(n)):
        print("Yes")
    else:
        print("No")

C#

using System;
 
namespace AdditivePrime
{
  class Program 
  {
    // Function to check whether a number is prime or not.
    static bool IsPrime(int n)
    {
      // Corner cases
      if (n <= 1) {
        return false;
      }
      // Suppose n=7 that is prime and its pair are (1,7)
      // so if a no. is prime then it can be checked by
      // numbers smaller than square root of the n
      for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
          return false;
        }
      }
 
      return true;
    }
 
    // Function to find the sum of the digits of a number.
    static int DigitSum(int n)
    {
      int ans = 0;
 
      while (n > 0) {
        ans += (n % 10);
        n /= 10;
      }
 
      return ans;
    }
 
    // Function to check whether a number is additive prime
    // or not.
    static bool IsAdditivePrime(int n)
    {
      if (IsPrime(n)) {
        int dSum = DigitSum(n);
 
        if (IsPrime(dSum)) {
          return true;
        }
      }
 
      return false;
    }
 
    static void Main(string[] args)
    {
      int n = 23;
 
      // Function Call
      if (IsAdditivePrime(n)) {
        Console.WriteLine("Yes");
      }
      else {
        Console.WriteLine("No");
      }
    }
  }
}
 
// This code is contributed by user_dtewbxkn77n

Javascript

// Function to check whether a number is prime or not.
function isPrime(n) {
  // Corner cases
  if (n <= 1) {
    return false;
  }
   
  // Suppose n=7 that is prime and its pair are (1,7)
  // So if a no. is prime then it can be checked by numbers smaller than square root
  // of the n
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
   
  return true;
}
 
// Function to find the sum of the digits of a number.
function digit_sum(n) {
  let ans = 0;
   
  while (n > 0) {
    ans += n % 10;
    n = Math.floor(n / 10);
  }
   
  return ans;
}
 
// Function to check whether a number is additive prime or
// not.
function additive_prime(n) {
  if (isPrime(n)) {
    const d_sum = digit_sum(n);
    if (isPrime(d_sum)) {
      return 1;
    }
  }
   
  return 0;
}
 
// Driver Code
const n = 23;
 
if (additive_prime(n)) {
  console.log("Yes");
} else {
  console.log("No");
}

Output

Yes

Time complexity: O(logn)
Auxiliary Space: O(1), as constant space is used.

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!