Given a number N, the task is to print the first N prime numbers.
Examples:
Input: N = 4
Output: 2, 3, 5, 7Input: N = 1
Output: 2
Approach 1:
The problem can be solved based on the following idea:
Start iterating from i = 2, till N prime numbers are found. For each i check if it is a prime or not and update the count of primes found till now.
Follow the steps mentioned below to implement the idea:
- Create a counter variable (say X = 0) to keep count of primes found till now and an iterator (say i) to iterate through the positive integers starting from 2.
- Iterate till X becomes N:
- Check if i is a prime or not.
- If it is a prime, print i and increase the value of X, otherwise, keep X unchanged.
- Increment the value of i by 1.
Below is the implementation of the above idea:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to generate first n primesvoid generatePrime(int n){ int X = 0, i = 2; bool flag; while(X < n){ flag = true; for(int j = 2; j <= sqrt(i); j++){ if (i%j == 0){ flag = false; break; } } if(flag){ cout << i << " "; X++; } i++; } cout << endl;}// Driver codeint main(){ // Test Case 1 int N = 4; // Function call generatePrime(N); // Test Case 2 N = 1; // Function call generatePrime(N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to generate first n primes static void generatePrime(int n) { int X = 0, i = 2; boolean flag; while(X < n){ flag = true; for(int j = 2; j <= (double)Math.sqrt(i); j++){ if (i%j == 0){ flag = false; break; } } if(flag){ System.out.print( i + " "); X++; } i++; } System.out.println();} // Driver code public static void main(String[] args) { // Test Case 1 int N = 4; // Function call generatePrime(N); // Test Case 2 N = 1; // Function call generatePrime(N); }} |
Python3
# Python code to implement the approachimport math# Function to generate first n primesdef generatePrime(n): X = 0 i = 2 flag = False while(X < n): flag = True for j in range(2, math.floor(math.sqrt(i)) + 1): if (i%j == 0): flag = False break if(flag): print(i, end=" ") X+=1 i+=1 print() # Driver code# Test Case 1N = 4# Function callgeneratePrime(N)# Test Case 2N = 1# Function callgeneratePrime(N)#This code is contributed by Shubham Singh |
C#
using System;using System.Linq;class GFG{ // Function to generate first n primes static void GeneratePrime(int n) { int X = 0, i = 2; bool flag; while (X < n) { flag = true; for (int j = 2; j <= Math.Sqrt(i); j++) { if (i % j == 0) { flag = false; break; } } if (flag) { Console.Write(i + " "); X++; } i++; } Console.WriteLine(); } // Driver code static void Main() { // Test Case 1 int N = 4; // Function call GeneratePrime(N); // Test Case 2 N = 1; // Function call GeneratePrime(N); }}// code by ksam24000 |
Javascript
// JS code to implement the approach// Function to generate first n primesfunction generatePrime( n){ let X = 0, i = 2; let flag; while(X < n){ flag = true; for(let j = 2; j <= Math.sqrt(i); j++){ if (i%j == 0){ flag = false; break; } } if(flag){ console.log(i); X++; } i++; } console.log("\n");}// Driver code// Test Case 1let N = 4;// Function callgeneratePrime(N);// Test Case 2N = 1;// Function callgeneratePrime(N); // This code is contributed by ratiagrawal. |
Output
2 3 5 7 2
Time Complexity: O(X * log X) where X is the largest prime
Auxiliary Space: O(1)
Approach 2:
Below code also generates the first N prime numbers, but it is more efficient than the previous code because it only checks odd numbers after 2, and only checks them for divisibility by previously found prime numbers. This reduces the number of iterations required in the loop, making the code faster for large values of N.
Below is the implementation of the above algorithm:
C++
// CPP program to generate and print first N prime numbers// using above approach#include <bits/stdc++.h>using namespace std;void generateprime(int N){ vector<int> primes; // Initialize an empty vector to // store prime numbers primes.push_back(2); // Add 2 as the first prime number int num = 3; // Start checking for prime numbers from 3 while (primes.size() < N) { // Keep searching until we // find N prime numbers bool is_prime = true; // Assume the current number is prime // until proven otherwise for (int i = 0; i < primes.size(); i++) { if (num % primes[i] == 0) { // If the current number is // divisible by any previously found // prime numbers is_prime = false; // Then it is not a prime // number break; // Exit the loop since we've already // proven it's not prime } } if (is_prime) { // If the current number is still // prime after checking all // previously found prime numbers primes.push_back(num); // Add it to our vector // of prime numbers } num += 2; // Check the next odd number (since even // numbers other than 2 are not prime) } for (int i = 0; i < primes.size(); i++) { // Print the first N prime numbers cout << primes[i] << " "; } cout << endl;}int main(){ // Test Case 1 int n = 4; generateprime(n); // Test Case 2 n = 1; generateprime(n); return 0;}// This code is contributed by Susobhan Akhuli |
Java
import java.util.*;public class Main {public static void generateprime(int N) {List<Integer> primes = new ArrayList<>(); // Initialize an empty list to store prime numbersprimes.add(2); // Add 2 as the first prime numberint num = 3; // Start checking for prime numbers from 3while (primes.size() < N) { // Keep searching until we find N prime numbersboolean is_prime = true; // Assume the current number is prime until proven otherwisefor (int i = 0; i < primes.size(); i++) {if (num % primes.get(i) == 0) { // If the current number is divisible by any previously found prime numbersis_prime = false; // Then it is not a prime numberbreak; // Exit the loop since we've already proven it's not prime}}if (is_prime) { // If the current number is still prime after checking all previously found prime numbersprimes.add(num); // Add it to our list of prime numbers}num += 2; // Check the next odd number (since even numbers other than 2 are not prime)}for (int i = 0; i < primes.size(); i++) { // Print the first N prime numbersSystem.out.print(primes.get(i) + " ");}System.out.println();}public static void main(String[] args) {// Test Case 1int n = 4;generateprime(n);// Test Case 2n = 1;generateprime(n);}} |
Python3
def generateprime(N): primes = [2] # Initialize an empty list to store prime numbers and add 2 as the first prime number num = 3 # Start checking for prime numbers from 3 while len(primes) < N: # Keep searching until we find N prime numbers is_prime = True # Assume the current number is prime until proven otherwise for i in range(len(primes)): if num % primes[i] == 0: # If the current number is divisible by any previously found prime numbers is_prime = False # Then it is not a prime number break # Exit the loop since we've already proven it's not prime if is_prime: # If the current number is still prime after checking all previously found prime numbers primes.append(num) # Add it to our list of prime numbers num += 2 # Check the next odd number (since even numbers other than 2 are not prime) for i in range(len(primes)): # Print the first N prime numbers print(primes[i], end=" ") print()# Test Case 1n = 4generateprime(n)# Test Case 2n = 1generateprime(n) |
C#
// C# program to generate and print first N prime numbers// using above approachusing System;using System.Collections.Generic;public class GFG { public static void Main() { // Test Case 1 int n = 4; GeneratePrime(n); // Test Case 2 n = 1; GeneratePrime(n); } public static void GeneratePrime(int n) { List<int> primes = new List<int>(); // Initialize an empty list // to store prime numbers primes.Add(2); // Add 2 as the first prime number int num = 3; // Start checking for prime numbers from 3 while (primes.Count < n) // Keep searching until we // find N prime numbers { bool isPrime = true; // Assume the current number is // prime until proven otherwise for (int i = 0; i < primes.Count; i++) { if (num % primes[i] == 0) // If the current number is // divisible by any previously // found prime numbers { isPrime = false; // Then it is not a // prime number break; // Exit the loop since we've // already proven it's not prime } } if (isPrime) // If the current number is still // prime after checking all // previously found prime numbers { primes.Add(num); // Add it to our list // of prime numbers } num += 2; // Check the next odd number (since // even numbers other than 2 are not // prime) } for (int i = 0; i < primes.Count; i++) // Print the first N prime numbers { Console.Write(primes[i] + " "); } Console.WriteLine(); }} |
Javascript
function generateprime(N){ let primes = []; // Initialize an empty array to store prime numbers primes.push(2); // Add 2 as the first prime number let num = 3; // Start checking for prime numbers from 3 while (primes.length < N) { // Keep searching until we // find N prime numbers let is_prime = true; // Assume the current number is // prime until proven otherwise for (let i = 0; i < primes.length; i++) { if (num % primes[i] == 0) { // If the current number is // divisible by any previously // found prime numbers is_prime = false; // Then it is not a prime // number break; // Exit the loop since we've already // proven it's not prime } } if (is_prime) { // If the current number is still // prime after checking all // previously found prime numbers primes.push(num); // Add it to our array of // prime numbers } num += 2; // Check the next odd number (since even // numbers other than 2 are not prime) } for (let i = 0; i < primes.length; i++) { // Print the first N prime numbers console.log(primes[i] + " "); } console.log("<br>");}// Test Case 1let n = 4;generateprime(n);// Test Case 2n = 1;generateprime(n);// This code is contributed by Susobhan Akhuli |
Output
2 3 5 7 2
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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!
