Additive Prime Number
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" ); } |
Yes
Time complexity: O(logn)
Auxiliary Space: O(1), as constant space is used.