Given an integer N, the task is to print all the multiplicative primes ? N.
Multiplicative Primes are the primes such that the product of their digits is also a prime. For example; 2, 3, 7, 13, 17, …
Examples:
Input: N = 10
Output: 2 3 5 7
Input: N = 3
Output: 2 3
Approach: Using Sieve of Eratosthenes check for all the primes ? N whether they are multiplicative primes i.e. product of their digits is also a prime. If yes then print those multiplicative primes.
Algorithm:
Step 1: Define a function of the static type which will return the int value and take input as an integer number and return the product of its digits.
Step 2: Now Initialize the variable of in type called prod with the initial value 1.
Step 3: Start a while loop which will calculate the product of digits:
a. Multiply prod by the remainder of n divided by 10.
b. Divide n by 10 and update the value of n with the result.
c. Repeat until n becomes 0.
Step 4: Now return prod as the digit product of n
Step 5: Create a function called printMultiplicativePrimes that outputs all multiplicative primes up to n given an integer input of n.
Step 6: Set every value in the prime boolean array, which has a size of n+1, to true during initialization.
Step 7: primes [0] and [1] should be set to false because they are not primes.
Step 8: Get all primes up to the square root of n using a for loop and Update all multiples of p by setting prime[i] to false if prime[p] is true.
Step 9: Print all prime multiplicative numbers up to n using another for loop and Print I if both prime[i] and prime[digitProduct(i)] are true.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the digit product of nint digitProduct(int n){ int prod = 1; while (n) { prod = prod * (n % 10); n = n / 10; } return prod;}// Function to print all multiplicative primes <= nvoid printMultiplicativePrimes(int n){ // Create a boolean array "prime[0..n+1]". A // value in prime[i] will finally be false // if i is Not a prime, else true. bool prime[n + 1]; memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } for (int i = 2; i <= n; i++) { // If i is prime and its digit sum is also prime // i.e. i is a multiplicative prime if (prime[i] && prime[digitProduct(i)]) cout << i << " "; }}// Driver codeint main(){ int n = 10; printMultiplicativePrimes(n);} |
Java
// Java implementation of the approachimport java.io.*;class GFG {// Function to return the digit product of nstatic int digitProduct(int n){ int prod = 1; while (n > 0) { prod = prod * (n % 10); n = n / 10; } return prod;}// Function to print all multiplicative primes <= nstatic void printMultiplicativePrimes(int n){ // Create a boolean array "prime[0..n+1]". A // value in prime[i] will finally be false // if i is Not a prime, else true. boolean prime[] = new boolean[n + 1 ]; for(int i = 0; i <= n; i++) prime[i] = true; prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } for (int i = 2; i <= n; i++) { // If i is prime and its digit sum is also prime // i.e. i is a multiplicative prime if (prime[i] && prime[digitProduct(i)]) System.out.print( i + " "); }} // Driver code public static void main (String[] args) { int n = 10; printMultiplicativePrimes(n); }}// This code is contributed by shs.. |
Python3
# Python 3 implementation of the approachfrom math import sqrt# Function to return the digit product of ndef digitProduct(n): prod = 1 while (n): prod = prod * (n % 10) n = int(n / 10) return prod# Function to print all multiplicative# primes <= ndef printMultiplicativePrimes(n): # Create a boolean array "prime[0..n+1]". # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [True for i in range(n + 1)] prime[0] = prime[1] = False for p in range(2, int(sqrt(n)) + 1, 1): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p for i in range(p * 2, n + 1, p): prime[i] = False for i in range(2, n + 1, 1): # If i is prime and its digit sum # is also prime i.e. i is a # multiplicative prime if (prime[i] and prime[digitProduct(i)]): print(i, end = " ")# Driver codeif __name__ == '__main__': n = 10 printMultiplicativePrimes(n)# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachclass GFG {// Function to return the digit product of nstatic int digitProduct(int n){ int prod = 1; while (n > 0) { prod = prod * (n % 10); n = n / 10; } return prod;}// Function to print all multiplicative primes <= nstatic void printMultiplicativePrimes(int n){ // Create a boolean array "prime[0..n+1]". A // value in prime[i] will finally be false // if i is Not a prime, else true. bool[] prime = new bool[n + 1 ]; for(int i = 0; i <= n; i++) prime[i] = true; prime[0] = prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } for (int i = 2; i <= n; i++) { // If i is prime and its digit sum is also prime // i.e. i is a multiplicative prime if (prime[i] && prime[digitProduct(i)]) System.Console.Write( i + " "); }} // Driver code static void Main() { int n = 10; printMultiplicativePrimes(n); }}// This code is contributed by chandan_jnu |
PHP
<?php// PHP implementation of the approach// Function to return the digit product of nfunction digitProduct($n){ $prod = 1; while ($n) { $prod = $prod * ($n % 10); $n = floor($n / 10); } return $prod;}// Function to print all multiplicative// primes <= nfunction printMultiplicativePrimes($n){ // Create a boolean array "prime[0..n+1]". // A value in prime[i] will finally be // false if i is Not a prime, else true. $prime = array_fill(0, $n + 1, true); $prime[0] = $prime[1] = false; for ($p = 2; $p * $p <= $n; $p++) { // If prime[p] is not changed, then // it is a prime if ($prime[$p]) { // Update all multiples of p for ($i = $p * 2; $i <= $n; $i += $p) $prime[$i] = false; } } for ($i = 2; $i <= $n; $i++) { // If i is prime and its digit sum is also // prime i.e. i is a multiplicative prime if ($prime[$i] && $prime[digitProduct($i)]) echo $i, " "; }}// Driver code$n = 10;printMultiplicativePrimes($n);// This code is contributed by Ryuga.?> |
Javascript
<script>// Javascript implementation of the approach // Function to return the digit product of n function digitProduct(n) { let prod = 1; while (n > 0) { prod = prod * (n % 10); n = Math.floor(n / 10); } return prod; } // Function to print all // multiplicative primes <= n function printMultiplicativePrimes(n) { // Create a boolean array "prime[0..n+1]". A // value in prime[i] will finally be false // if i is Not a prime, else true. let prime = new Array(n + 1); for(let i = 0; i <= n; i++) prime[i] = true; prime[0] = prime[1] = false; for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) prime[i] = false; } } for (let i = 2; i <= n; i++) { // If i is prime and its digit sum is also prime // i.e. i is a multiplicative prime if (prime[i] && prime[digitProduct(i)]) document.write( i + " "); } } // Driver code let n = 10; printMultiplicativePrimes(n); // This code is contributed by unknown2108 </script> |
2 3 5 7
Time Complexity: O(n3/2)
Auxiliary Space: O(n)
