CommonLounge Archive

Sieve of Eratosthenes tutorial

March 21, 2017

Sieve of Eratosthenes is a way to compute prime factors of a number by pre-computing the smallest prime-factors of all numbers till a limit.

A great video tutorial by Khan Academy -

Also I recommend you to read this blog on CodeForces - Prime Factorization In log(n) After Sieves

All these algorithms take O(n log n) time. This can be also done in time O(n). See here - Sieve of Eratosthenes in 0(n) time complexity

© 2016-2022. All rights reserved.