Prime Numbers / Sieve
Learn Prime Numbers / Sieve (Foundations, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Prime Numbers and the Sieve of Eratosthenes A prime has exactly two divisors, 1 and itself. To test one number, try divisors only up to √n , which takes O(√n). To find all primes up to n, the Sieve of Eratosthenes crosses out the multiples of each prime, starting at p², in about O(n log log n) .