The Sieve of Eratosthenes for Prime Numbers with Python and Java Code

Posted on by

The Sieve of Eratosthenes is a popular algorithm used to find all prime numbers up to a given limit. It is an efficient method that eliminates multiples of each prime number as it iterates through the numbers.

Python Code


def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
primes[0] = primes[1] = False

for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False

return [x for x in range(n+1) if primes[x]]

n = 100
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

Java Code:

import java.util.Arrays;

public class SieveOfEratosthenes {
public static void sieveOfEratosthenes(int n) {
boolean[] primes = new boolean[n+1];
Arrays.fill(primes, true);
primes[0] = primes[1] = false;

for (int i = 2; i <= Math.sqrt(n); i++) {
if (primes[i]) {
for (int j = i*i; j <= n; j += i) {
primes[j] = false;
}
}
}

for (int i = 0; i <= n; i++) {
if (primes[i]) {
System.out.print(i + " ");
}
}
}

public static void main(String[] args) {
int n = 100;
sieveOfEratosthenes(n);
}
}

The Python code above demonstrates how to implement the Sieve of Eratosthenes algorithm in Python. It starts by initializing a boolean list called “primes” with all values set to True. Then, it iterates through the numbers from 2 to the square root of the given limit. For each prime number found, it marks all its multiples as False in the “primes” list. Finally, it returns a list of all numbers up to the given limit that are marked as True.

The Java code follows a similar logic. It uses a boolean array called “primes” to keep track of prime numbers. It initializes all values to true, and then iterates through the numbers from 2 to the square root of the given limit. It marks all multiples of each prime number as false in the “primes” array. Finally, it prints out the prime numbers found.

Both implementations of the Sieve of Eratosthenes provide an efficient way to find prime numbers up to a given limit. They are useful when dealing with large sets of numbers and can be easily adapted to fit different programming languages.