Given a number n, we need to find the product of all prime numbers between 1 to n.
Examples:
Input: 5
Output: 30
Explanation: product of prime numbers between 1 to 5 is 2 * 3 * 5 = 30
Input : 7
Output : 210
Approach: Basic brute-force method
Steps:
- Initialize the product to be 1 and an empty list of primes.
- Iterate through all numbers i between 2 and n (inclusive).
- For each i, check if it is prime by iterating through all numbers j between 2 and i-1 (inclusive) and checking if i is divisible by j. If i is not divisible by any j, it is prime, so append i to the list of primes and multiply it with the running product.
- Return the product of all primes.
C++
#include <iostream>#include <vector> // include vector library for storing prime numbersusing namespace std;// function to check if a number is primebool is_prime(int num) { if (num < 2) { // if number is less than 2, it's not a prime number return false; } for (int i = 2; i < num; i++) { // iterate over numbers from 2 to num-1 if (num % i == 0) { // if num is divisible by i, it's not a prime number return false; } } return true; // if num is not divisible by any number in the range, it's a prime number}// function to calculate the product of all prime numbers from 2 to nint product_of_primes(int n) { int product = 1; vector<int> primes; // create a vector to store prime numbers for (int i = 2; i <= n; i++) { // iterate over numbers from 2 to n if (is_prime(i)) { // check if i is a prime number primes.push_back(i); // add i to the vector of prime numbers product *= i; // multiply i to the product of all prime numbers so far } } return product; // return the product of all prime numbers}int main() { cout << product_of_primes(5) << endl; // Output: 30 return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class PrimeProduct { // Function to check if a number is prime public static boolean isPrime(int num) { if (num < 2) { // If the number is less than 2, it's not a prime number return false; } for (int i = 2; i < num; i++) { // Iterate over numbers from 2 to num-1 if (num % i == 0) { // If num is divisible by i, it's not a prime number return false; } } return true; // If num is not divisible by any number in the range, it's a prime number } // Function to calculate the product of all prime numbers from 2 to n public static int productOfPrimes(int n) { int product = 1; List<Integer> primes = new ArrayList<>(); // Create a list to store prime numbers for (int i = 2; i <= n; i++) { // Iterate over numbers from 2 to n if (isPrime(i)) { // Check if i is a prime number primes.add(i); // Add i to the list of prime numbers product *= i; // Multiply i to the product of all prime numbers so far } } return product; // Return the product of all prime numbers } public static void main(String[] args) { System.out.println(productOfPrimes(5)); // Output: 30 }} |
Python3
def is_prime(num): if num < 2: return False for i in range(2, num): if num % i == 0: return False return Truedef product_of_primes(n): product = 1 primes = [] for i in range(2, n+1): if is_prime(i): primes.append(i) product *= i return productprint(product_of_primes(5)) # Output: 30 |
C#
using System;using System.Collections.Generic;class Program{ // Function to check if a number is prime static bool IsPrime(int num) { if (num < 2) { // If the number is less than 2, it's not a prime number return false; } for (int i = 2; i < num; i++) { // Iterate over numbers from 2 to num-1 if (num % i == 0) { // If num is divisible by i, it's not a prime number return false; } } // If num is not divisible by any number in the range, it's a prime number return true; } // Function to calculate the product of all prime numbers from 2 to n static int ProductOfPrimes(int n) { int product = 1; List<int> primes = new List<int>(); // Create a list to store prime numbers for (int i = 2; i <= n; i++) { // Iterate over numbers from 2 to n if (IsPrime(i)) { // Check if i is a prime number primes.Add(i); // Add i to the list of prime numbers product *= i; // Multiply i with the product of all prime numbers so far } } return product; // Return the product of all prime numbers } static void Main() { Console.WriteLine(ProductOfPrimes(5)); // Output: 30 }}// This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
function is_prime(num) { if (num < 2) { return false; } for (let i = 2; i < num; i++) { if (num % i === 0) { return false; } } return true;}function product_of_primes(n) { let product = 1; let primes = []; for (let i = 2; i <= n; i++) { if (is_prime(i)) { primes.push(i); product *= i; } } return product;}console.log(product_of_primes(5)); // Output: 30 |
Output
30
The time complexity of this approach is O(n^2).
The auxiliary space is O(n).
Efficient Approach:
Using Sieve of Eratosthenes to find all prime numbers from 1 to n then compute the product.
Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
When the algorithm terminates, all the numbers in the list that are not marked are prime and using a loop we compute the product of prime numbers.
When the algorithm terminates, all the numbers in the list that are not marked are prime and using a loop we compute the product of prime numbers.
C++
// CPP Program to find product// of prime numbers between 1 to n#include <bits/stdc++.h>using namespace std;// Returns product of primes in range from// 1 to n.long ProdOfPrimes(int n){ // Array to store prime numbers bool prime[n + 1]; // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. memset(prime, true, n + 1); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Return product of primes generated // through Sieve. long prod = 1; for (int i = 2; i <= n; i++) if (prime[i]) prod *= i; return prod;}// Driver codeint main(){ int n = 10; cout << ProdOfPrimes(n); return 0;} |
Java
// Java Program to find product// of prime numbers between 1 to nimport java.util.Arrays;class GFG { // Returns product of primes in range from // 1 to n. static long ProdOfPrimes(int n) { // Array to store prime numbers boolean prime[]=new boolean[n + 1]; // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. Arrays.fill(prime, true); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Return product of primes generated // through Sieve. long prod = 1; for (int i = 2; i <= n; i++) if (prime[i]) prod *= i; return prod; } // Driver code public static void main (String[] args) { int n = 10; System.out.print(ProdOfPrimes(n)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 Program to find product# of prime numbers between 1 to n# Returns product of primes # in range from 1 to n.def ProdOfPrimes(n): # Array to store prime numbers prime = [True for i in range(n + 1)] # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. p = 2 while(p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p i = p * 2 while(i <= n): prime[i] = False i += p p += 1 # Return product of primes # generated through Sieve. prod = 1 for i in range(2, n+1): if (prime[i]): prod *= i return prod# Driver coden = 10print(ProdOfPrimes(n))# This code is contributed by Anant Agarwal. |
C#
// C# Program to find product of// prime numbers between 1 to nusing System;public class GFG { // Returns product of primes // in range from 1 to n. static long ProdOfPrimes(int n) { // Array to store prime numbers bool []prime=new bool[n + 1]; // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. for(int i = 0; i < n + 1; i++) prime[i] = true; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Return product of primes generated // through Sieve. long prod = 1; for (int i = 2; i <= n; i++) if (prime[i]) prod *= i; return prod; } // Driver code public static void Main () { int n = 10; Console.Write(ProdOfPrimes(n)); }}// This code is contributed by Sam007 |
Javascript
<script> // Javascript Program to find product of // prime numbers between 1 to n // Returns product of primes // in range from 1 to n. function ProdOfPrimes(n) { // Array to store prime numbers let prime = new Array(n + 1); prime.fill(0); // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. for(let i = 0; i < n + 1; i++) prime[i] = true; for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) prime[i] = false; } } // Return product of primes generated // through Sieve. let prod = 1; for (let i = 2; i <= n; i++) if (prime[i]) prod *= i; return prod; } let n = 10; document.write(ProdOfPrimes(n)); </script> |
PHP
<?php// PHP Program to find product// of prime numbers between 1 to n// Returns product of primes // in range from 1 to n.function ProdOfPrimes($n){ // Array to store prime // numbers Create a boolean // array "prime[0..n]" and // initialize all entries it // as true. A value in prime[i] // will finally be false if i // is Not a prime, else true. $prime = array(); for($i = 0; $i < $n + 1; $i++) $prime[$i] = true; for ($p = 2; $p * $p <= $n; $p++) { // If prime[p] is not changed, // then it is a prime if ($prime[$p] == true) { // Update all multiples of p for ($i = $p * 2; $i <= $n; $i += $p) $prime[$i] = false; } } // Return product of primes // generated through Sieve. $prod = 1; for ($i = 2; $i <= $n; $i++) if ($prime[$i]) $prod *= $i; return $prod;}// Driver Code$n = 10;echo (ProdOfPrimes($n));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Output
210
Time Complexity: O(n log log n) // for sieve of erastosthenes
Auxiliary Space: O(N) //an extra array is used to store all the prime numbers hence algorithm takes up linear space
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!
