3 ms·
One of the first algorithms I implemented in Python was the prime sieve. I used it extensively when solving Project Euler problems as well. Good days :)
by Cyph0n 11y ago
One of the first algorithms I implemented in Python was the prime sieve. I used it extensively when solving Project Euler problems as well. Good days :)
- nroets 11y agoYou can solve much more problems from Project Euler using a DFS variation of the Sieve of Euler. It is a depth first search of all the numbers less than n. It visits every number exactly once. When it visits a number, the prime factorization of the number is available (or any quantity derived from the factorization, like Euler's phi function). And it uses no divisions. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27s_Sieve https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27...