This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.


The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.



Task

Implement the   Sieve of Eratosthenes   algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found.

That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

If there's an easy way to add such a wheel based optimization, implement it as an alternative version.



Note

 It is important that the sieve algorithm be the actual algorithm used to find prime numbers for the task.


Related tasks

   Emirp primes
   count in factors
   prime decomposition
   factors of an integer
   extensible prime generator
   primality by trial division
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


                           000F4240  0000     1 n=1000*1000
                               0000  0000     2 .entry	main,0
                            7E 7CFD  0002     3 	clro	-(sp)			;result buffer
                            5E   DD  0005     4 	pushl	sp			;pointer to buffer
                            10   DD  0007     5 	pushl	#16			;descriptor -> len of buffer
                                     0009     6 
                            02   DD  0009     7 	pushl	#2			;1st candidate
                                     000B     8 test:
                 09 46'AF   6E   E1  000B     9 	bbc	(sp), b^bits, found	;bc - bit clear
                                     0010    10 next:
           F3 6E   000F4240 8F   F2  0010    11         aoblss  #n, (sp), test		;+1: limit,index
                                 04  0018    12         ret
                                     0019    13 found:
                         04 AE   7F  0019    14 	pushaq	4(sp)			;-> descriptor by ref
                         04 AE   DF  001C    15 	pushal	4(sp)			;-> prime on stack by ref
              00000000'GF   02   FB  001F    16 	calls	#2, g^ots$cvt_l_ti	;convert integer to string
                         04 AE   7F  0026    17 	pushaq	4(sp)			;
              00000000'GF   01   FB  0029    18 	calls	#1, g^lib$put_output	;show result
                                     0030    19 
                       53   6E   D0  0030    20 	movl	(sp), r3
                                     0033    21 mult:
    0002 53   6E   000F4240 8F   F1  0033    22 	acbl    #n, (sp), r3, set_mult	;limit,add,index
                            D1   11  003D    23 	brb	next
                                     003F    24 set_mult:				;set bits for multiples
                 EF 46'AF   53   E2  003F    25 	bbss	r3, b^bits, mult	;branch on bit set & set
                            ED   11  0044    26 	brb	mult
                                     0046    27 
                           0001E892  0046    28 bits:	.blkl	<n+2+31>/32
                                     E892    29 .end	main