News for hackers. Stuff that matters.
Re:Dijkstra's Prime Number Algorithm by amelius on Tuesday April 05, 2016 @07:55AM (#11429642)
> 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

Re:Dijkstra's Prime Number Algorithm by cdman on Tuesday April 05, 2016 @08:56AM (#11429965)
From the article: "this algorithm is an interesting mix between the Erathosenes Sieve..."
Re:Dijkstra's Prime Number Algorithm by heinrichhartman on Tuesday April 05, 2016 @08:13AM (#11429723)
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.

Re:Dijkstra's Prime Number Algorithm by davidamarquis on Tuesday April 05, 2016 @12:31PM (#11431812)
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.

Re:Dijkstra's Prime Number Algorithm by Cyph0n on Tuesday April 05, 2016 @08:11AM (#11429706)
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 :)
Re:Dijkstra's Prime Number Algorithm by nroets on Tuesday April 05, 2016 @08:28AM (#11429801)
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...