Sieve of Eratosthenes
Sieve of Eratosthenes
The Sieve of Eratosthenes is an ancient and highly efficient algorithm for finding all prime numbers up to a given limit N. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given a positive integer N, find and print all prime numbers from 2 to N inclusive. Example: N=30 → "2 3 5 7 11 13 17 19 23 29"
Input format — only if your code reads from stdin
Input format: - A single integer N Output: all prime numbers from 2 to N, space-separated on a single line. If N < 2, print an empty line.
Approach
Create a boolean array isPrime[0..N] initialized to true. Set isPrime[0]=isPrime[1]=false. For each p from 2 to √N: if isPrime[p] is true, mark all multiples of p (starting from p²) as false. Collect and print all indices where isPrime is still true.
Input
Output
- •
1 ≤ N ≤ 10^6
More Algorithms problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards