Simple Sieve - DSA

🧮 A Simple Sieve of Eratosthenes in Java: Find All Primes Up to N

"The prime numbers are the building blocks of all natural numbers."

— Carl Friedrich Gauss

Prime numbers play a fundamental role in number theory and cryptography. In this post, we'll walk through the Sieve of Eratosthenes — a simple and efficient algorithm to generate all prime numbers up to a given number n.

We'll cover:

• ✅ What the sieve is
• 🧠 How it works
• 🔧 Java implementation (with fixed code)
• 🌍 Real-life applications of primes

📌 What Is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is a classic algorithm used to find all prime numbers less than a given integer n. It does so by iteratively marking the multiples of each prime starting from 2.

Time Complexity: O(n log log n)

Space Complexity: O(n)

💡 How Does It Work?

1. Create a boolean array of size n + 1, initialized to true. Each index represents a number.
2. Starting from 2, for each number, if it is marked true, mark all its multiples as false.
3. At the end, all indices with true are prime.

🧪 Java Implementation

Here's a clean and corrected version of the sieve algorithm in Java:

import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // Input the upper limit boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } System.out.println("Prime numbers up to " + n + " are:"); for (int i = 2; i <= n; i++) { if (isPrime[i]) { System.out.print(i + " "); } } } } 

🔍 Fixes Made to the Original Code

• Replaced undeclared variable num with n
• Fixed syntax error: === → == (Java uses == for comparison)
• Included primes up to n (inclusive)
• Set isPrime[0] and isPrime[1] to false explicitly
• Used Arrays.fill() for simplicity and clarity

🌍 Real-Life Applications of Prime Numbers

🔐 Cryptography & Cybersecurity

Public-key encryption algorithms like RSA use large primes for secure key generation.

🎲 Random Number Generation

Primes are used in linear congruential generators and hash functions to produce uniform randomness.

💽 Hashing Algorithms

Prime table sizes reduce hash collisions, improving performance in hash tables and bloom filters.

🎮 Procedural Generation in Graphics

Games use prime intervals to generate less predictable world seeds and layouts.

📊 Mathematical Research & Theories

The study of primes leads to groundbreaking theorems and conjectures (e.g., Goldbach's, Riemann Hypothesis).

🚀 Try It Out Yourself

You can run the above code on any online Java compiler:

• 🔗 Replit
• 🔗 JDoodle
• 🔗 OnlineGDB

Just copy-paste the code, input a number like 100, and watch the primes roll out!