Prime numbers using Sieve of Eratosthenes
A prime number is a natural number greater than 1 and is divisible by only 1 and itself.
Generating primes fast is very important in some problems. You can use the Sieve of Eratosthenes to find all the prime numbers that are less than or equal to a given number N or to find out whether a number is a prime number in more efficient way.
The basic idea behind the Sieve of Eratosthenes is that at each iteration one prime number is picked up and all its multiples are eliminated. After the elimination process is complete, all the unmarked numbers that remain are prime.
- Create a list of numbers from 2 to the desired limit.
- Start with the first number (2) and mark it as prime.
- Eliminate all multiples of the current prime number from the list.
- Find the next unmarked number in the list and set it as the new prime.
- Repeat steps 3-4 until the square of the current prime is greater than the limit.
- All remaining unmarked numbers in the list are prime.
Below is the code snippet for Sieve of Eratosthenes:
#include <iostream>
#include <vector>
using namespace std;
void sieve(int N) {
bool isPrime[N + 1];
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= N; ++i) {
// If i is prime
if (isPrime[i] == true) {
// Mark all the multiples of i as composite numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
cout << "Prime numbers up to " << N << ": ";
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
int main() {
// Limit the sieve to generate prime numbers up to 50
int N = 50;
sieve(N);
return 0;
}
import java.io.*;
public class GFG {
// Function to find prime numbers up to N using
// Sieve of Eratosthenes
public static void sieve(int N) {
// Create a boolean array to store prime flags for numbers up to N
boolean[] isPrime = new boolean[N + 1];
// Initialize all elements of the array as true
// assuming all numbers are prime initially
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
// 0 and 1 are not prime
// so mark them as false
isPrime[0] = false;
isPrime[1] = false;
// Iterate from 2 to the square root of N
for (int i = 2; i * i <= N; ++i) {
// If the current number is prime
if (isPrime[i]) {
// Mark all the multiples of i as composite numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
System.out.println("Prime numbers up to " + N + ":");
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
public static void main(String[] args) {
// Define the upper limit for finding prime numbers
int N = 50;
// Call the sieve function to find prime numbers up to N
sieve(N);
}
}
def sieve(N):
# Creating an array to store prime status of numbers from 0 to N
isPrime = [True] * (N + 1)
# Marking 0 and 1 as non-prime
isPrime[0] = False
isPrime[1] = False
# Iterating from 2 to sqrt(N)
for i in range(2, int(N ** 0.5) + 1):
# If current number is prime
if isPrime[i]:
# Marking multiples of i as non-prime
for j in range(i * i, N + 1, i):
isPrime[j] = False
# Print prime numbers
print("Prime numbers up to", N, ":")
for num, prime in enumerate(isPrime):
if prime:
print(num),
print("") # Empty print statement for newline
# Example usage:
N = 20 # Define the range for prime checking
sieve(N) # Call the function to sieve primes
using System;
public class Program {
// Declaring isPrime array outside of the Sieve method
private static bool[] isPrime;
public static void Sieve(int N)
{
isPrime = new bool[N + 1];
// Initializing all elements as true
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
// Iterate through numbers starting from 2 up to
// square root of N
for (int i = 2; i * i <= N; ++i) {
// If i is a prime number
if (isPrime[i]) {
// Mark all the multiples of i as composite
// numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// At this point, isPrime array will contain true
// for prime numbers and false for composite numbers
}
public static void Main(string[] args)
{
int N
= 100; // Example: Find prime numbers up to 100
Sieve(N);
Console.WriteLine("Prime numbers up to " + N + ":");
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
Console.Write(i + " ");
}
}
}
}
function sieve(N) {
// Create a boolean array to store prime flags for numbers up to N
let isPrime = new Array(N + 1).fill(true);
// 0 and 1 are not prime
// so mark them as false
isPrime[0] = false;
isPrime[1] = false;
// Iterate from 2 to the square root of N
for (let i = 2; i * i <= N; ++i) {
// If the current number is prime
if (isPrime[i]) {
// Mark all the multiples of i as composite numbers
for (let j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
let primes = [];
for (let i = 2; i <= N; ++i) {
if (isPrime[i]) {
primes.push(i);
}
}
console.log("Prime numbers up to " + N + ":");
console.log(primes.join(" ")); // Join prime numbers into a single string
//separated by space
}
// Define the upper limit for finding prime numbers
let N = 50;
// Call the sieve function to find prime numbers up to N
sieve(N);
Output
Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)