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, |
## 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 __riddlesbrand.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!