Programming

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

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.

wisdomiseme.com

Recent Posts

Unlocking the Mystery of Irrational Numbers: A Fun Guide for Young Mathematicians

Introduction Have you ever wondered about numbers that don't quite fit in with the rest?…

4 months ago

Trick by which you will never forget capital of Sudan

Struggling to remember the capitals of countries? Well, you’re not alone. Today, we’re going to…

6 months ago

(¿) Upside down question mark shortcut for Ms Word [2024]

Works with Microsoft® Word® 2010, 2013, 2016, 2019, 2021, 365 and above Upside down question mark (¿)…

7 months ago

How to convert text to formula in Excel

We know an Excel function "FORMULATEXT" which converts Formula into Text. What if you want…

8 months ago

Nabla Symbol (∇) in MS Word and its shortcut

Microsoft Word has different ways to add symbol. Nabla symbol (∇) is one of the…

8 months ago

Remapping Keys in Windows using PowerToys

Broken keys in your keyboard or just want to remap keys in Windows no need…

8 months ago