|
I want to print out, in order, all prime numbers in the range [1,n], for
an input n. Can this be done in O(n) time? If not, prove your
answer. If yes, provide an algorithm with a proof of correctness.
For the purpose of this question, assume that the computing machine you are working with can store only integers (no real-number support), and the integers it can store are only those in the range [0,n] (no unlimited word-size support). Other than these two restrictions, it follows the usual complexity assumptions. (So, for example, it is able to print out any number in the range [0,n] in O(1) time, which is not possible for a real machine to do.) |
List of solvers:Uoti Urpala (1 January 05:39)Shizhe Zhao (1 January 21:39) Tianyi Zhang (2 January 17:07) Lin Jin (3 January 20:54) Mithil Ramteke (7 January 04:58) JJ Rabeyrin (15 January 08:18) Jim Boyce (16 January 03:32) Nis Jørgensen (19 January 09:09) Mengxiao Zhang (26 January 00:30) Oscar Volpatti (30 January 18:59) Andreas Stiller (1 February 01:59) |
Elegant and original solutions can be submitted to the puzzlemaster at riddles
brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!