aloalgoPrime Numbers & Sieve
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are fundamental in number theory and appear in many coding interview problems.Primality Testing
To check if a number n is prime, we only need to check divisors up to sqrt(n). If n has a factor larger than sqrt(n), it must also have a factor smaller than sqrt(n).Sieve of Eratosthenes
The Sieve of Eratosthenes is an efficient algorithm to find all primes up to n. It works by iteratively marking the multiples of each prime starting from 2.Counting Primes
Prime Factorization
Every integer greater than 1 can be uniquely represented as a product of prime factors (Fundamental Theorem of Arithmetic).Unique Prime Factors with Counts
Finding All Divisors
Smallest Prime Factor (SPF)
A modified sieve that stores the smallest prime factor for each number. Useful for fast factorization of multiple numbers.Complexity Summary
| Algorithm | Time | Space |
|---|---|---|
| Primality Test | O(sqrt(n)) | O(1) |
| Sieve of Eratosthenes | O(n log log n) | O(n) |
| Prime Factorization | O(sqrt(n)) | O(log n) |
| Find All Divisors | O(sqrt(n)) | O(sqrt(n)) |
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.