Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by amelius | Hacker News Reader

Full thread

amelius·

> What is remarkable about this algorithm is, that it uses no divisions at all!

The same holds for the Sieve of Eratosthenes [1]

[1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

View on HN

From the article: "this algorithm is an interesting mix between the Erathosenes Sieve..."

Author here: Yes, that true, thanks for pointing it out. [In fact, Erathosthenes is mentioned later in that note.]

I still find it remarkable, that you can avoid divisions, while not to computing all multiples up-front and marking the results in a large table.

The algorithm is very nice. But I think you should think about what it means to divide one integer by another. The quotient of that operation is an integer. The remainder is an integer.

Can you express the number in terms of the quotient and remainder?

Using this expression write an algorithm that outputs the quotient and remainder using only addition, multiplication and checking equality with integers.

I think doing this would make the algorithm seem less surprising.

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 :)

You 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.27...

Reply on news.ycombinator.com