Given a positive integer N, calculate the product of the first N prime numbers.
Examples:
Input : N = 3 Output : 30 Explanation : First 3 prime numbers are 2, 3, 5. Input : N = 5 Output : 2310
Approach:
- Create a sieve which will help us to identify if the number is prime or not in O(1) time.
- Run a loop starting from 1 until and unless we find n prime numbers.
- Multiply all the prime numbers and neglect those which are not prime.
- Then, display the product of 1st N prime numbers.
Time Complexity – O( Nlog(logN) )
Below is the implementation of above approach:
C++
// C++ implementation of above solution#include "cstring"#include <iostream>using namespace std;#define MAX 10000// 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.bool prime[MAX + 1];void SieveOfEratosthenes(){ memset(prime, true, sizeof(prime)); prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// find the product of 1st N prime numbersint solve(int n){ // count of prime numbers int count = 0, num = 1; // product of prime numbers long long int prod = 1; while (count < n) { // if the number is prime add it if (prime[num]) { prod *= num; // increase the count count++; } // get to next number num++; } return prod;}// Driver codeint main(){ // create the sieve SieveOfEratosthenes(); int n = 5; // find the value of 1st n prime numbers cout << solve(n); return 0;} |
Java
// Java implementation of above solutionclass GFG{ static int MAX=10000; // 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. static boolean[] prime=new boolean[MAX + 1]; static void SieveOfEratosthenes(){ prime[1] = true; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == false) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } }}// find the product of 1st N prime numbersstatic int solve(int n){ // count of prime numbers int count = 0, num = 1; // product of prime numbers int prod = 1; while (count < n) { // if the number is prime add it if (!prime[num]) { prod *= num; // increase the count count++; } // get to next number num++; } return prod;}// Driver codepublic static void main(String[] args){ // create the sieve SieveOfEratosthenes(); int n = 5; // find the value of 1st n prime numbers System.out.println(solve(n));}}// This code is contributed by mits |
C#
// C# implementation of above solutionclass GFG{ static int MAX=10000; // 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. static bool[] prime=new bool[MAX + 1]; static void SieveOfEratosthenes(){ prime[1] = true; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == false) { // Set all multiples of p to non-prime for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } }}// find the product of 1st N prime numbersstatic int solve(int n){ // count of prime numbers int count = 0, num = 1; // product of prime numbers int prod = 1; while (count < n) { // if the number is prime add it if (!prime[num]) { prod *= num; // increase the count count++; } // get to next number num++; } return prod;}// Driver codepublic static void Main(){ // create the sieve SieveOfEratosthenes(); int n = 5; // find the value of 1st n prime numbers System.Console.WriteLine(solve(n));}}// This code is contributed by mits |
Python
'''python3 implementation of above solution'''import math as mtMAX=10000'''Create a boolean array "prime[0..n]" and initializeall entries it as true. A value in prime[i] willfinally be false if i is Not a prime, else true.'''prime=[True for i in range(MAX+1)]def SieveOfErastosthenes(): prime[1]=False for p in range(2,mt.ceil(mt.sqrt(MAX))): #if prime[p] is not changes, then it is a prime if prime[p]: #set all multiples of p to non-prime for i in range(2*p,MAX+1,p): prime[i]=False #find the product of 1st N prime numbersdef solve(n): #count of prime numbers count,num=0,1 #product of prime numbers prod=1 while count<n: #if the number is prime add it if prime[num]: prod*=num #increase the count count+=1 num+=1 return prod#Driver code#create the sieveSieveOfErastosthenes()n=5#find the value of 1st n prime numbersprint(solve(n))#this code is contributed by Mohit Kumar 29 |
PHP
<?php // PHP implementation of above solution$MAX = 10000;// 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_fill(0, $MAX + 1, true);function SieveOfEratosthenes(){ global $MAX; global $prime; $prime = array_fill(0, $MAX + 1, true); $prime[1] = false; for ($p = 2; $p * $p <= $MAX; $p++) { // If $prime[$p] is not changed, // then it is a $prime if ($prime[$p] == true) { // Set all multiples of $$p to non-$prime for ($i = $p * 2; $i <= $MAX; $i += $p) $prime[$i] = false; } }}// find the product of 1st N $prime numbersfunction solve($n){ global $prime; // $count of $prime numbers $count = 0; $num = 1; // product of $prime numbers $prod = 1; while ($count < $n) { // if the number is $prime add it if ($prime[$num]== true) { $prod *= $num; // increase the $count $count++; } // get to next number $num++; } return $prod;}// Driver code// create the sieveSieveOfEratosthenes();$n = 5;// find the value of 1st $n $prime numbersecho solve($n);// This code is contributed by ihritik?> |
Javascript
<script>// Javascript implementation of above solutionlet MAX = 10000;// 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.let prime = new Array(MAX + 1).fill(true);function SieveOfEratosthenes(){ prime[1] = false; for (let p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Set all multiples of p to non-prime for (let i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// find the product of 1st N prime numbersfunction solve(n){ // count of prime numbers let count = 0; let num = 1; // product of prime numbers let prod = 1; while (count < n) { // if the number is prime add it if (prime[num]== true) { prod *= num; // increase the count count++; } // get to next number num++; } return prod;}// Driver code// create the sieveSieveOfEratosthenes();let n = 5;// find the value of 1st n prime numbersdocument.write(solve(n));// This code is contributed by Saurabh Jaiswal</script> |
Output:
2310
Auxiliary Space: O(MAX)
NOTE: For larger values of N, the product may be give integer overflow errors.
Also for multiple queries, prefix array technique can be used which will give output of each query in O(1) after making the prefix array first which will take O(N) time.
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!
