sieve.py

# ------------------------------------------------------------------------- *
# * This is the classic prime sieve of Eratosthenes - a simple algorithm      *
# * that finds all the prime numbers between 2 and the constant 'N'.          * 
# *                                                                           *
# * Name            : sieve.c  (Sieve of Eratosthenes)                        *
# * Author          : Steve Park & Dave Geyer                                 *
# * Language        : ANSI C                                                  *
# * Latest Revision : 9-15-96                                                 *
#   Translated by   : Philip Steele 
#   Language        : Python 3.3
#   Latest Revision : 3/26/14
# * ------------------------------------------------------------------------- */

#include <stdio.h>
#include <math.h>  
from math import sqrt                    

N = 46341                 # limited only by memory size   */
SQRTN = int(sqrt(N))

############################Main Program#######################################
prime = [None for i in range(0,N+1)] # n is prime <=> prime[n] == 1  */
n = None                             # index of possible primes      */
s = None                             # step index                    */
t = 0                                # index used for tabular output */

prime[0] = 0                       # initialize the sieve */
prime[1] = 0
for n in range(2,N+1):       
  prime[n] = 1

for n in range(2,SQRTN+1):         # search all possibilities       */
  if (prime[n]):                      # if n is prime,                 */
    for s in range(2,int(N/n)+1):     # 2n, 3n, 4n ...  can't be prime */
      prime[s * n] = 0

print("\tThe primes between 2 and {0:1d} are\n".format(N))
for n in range(2,N+1):
  if (prime[n]):
    if (t == 0):
      print("\t", end='')
    print("{0:7d}".format(n), end='')
    t = (t + 1) % 10
    if (t == 0):
      print("")
  
print("")

# C output (first and last several lines):
# The primes between 2 and 46341 are

#  2      3      5      7     11     13     17     19     23     29
# 31     37     41     43     47     53     59     61     67     71
# 73     79     83     89     97    101    103    107    109    113
# 127    131    137    139    149    151    157    163    167    173
# 179    181    191    193    197    199    211    223    227    229
# 233    239    241    251    257    263    269    271    277    281
# 283    293    307    311    313    317    331    337    347    349
# 353    359    367    373    379    383    389    397    401    409
# 419    421    431    433    439    443    449    457    461    463
# 467    479    487    491    499    503    509    521    523    541
# 547    557    563    569    571    577    587    593    599    601
# 607    613    617    619    631    641    643    647    653    659
# 661    673    677    683    691    701    709    719    727    733
# 739    743    751    757    761    769    773    787    797    809
# 811    821    823    827    829    839    853    857    859    863
# 877    881    883    887    907    911    919    929    937    941
# 947    953    967    971    977    983    991    997   1009   1013
# ..................................................................
# 44453  44483  44491  44497  44501  44507  44519  44531  44533  44537
# 44543  44549  44563  44579  44587  44617  44621  44623  44633  44641
# 44647  44651  44657  44683  44687  44699  44701  44711  44729  44741
# 44753  44771  44773  44777  44789  44797  44809  44819  44839  44843
# 44851  44867  44879  44887  44893  44909  44917  44927  44939  44953
# 44959  44963  44971  44983  44987  45007  45013  45053  45061  45077
# 45083  45119  45121  45127  45131  45137  45139  45161  45179  45181
# 45191  45197  45233  45247  45259  45263  45281  45289  45293  45307
# 45317  45319  45329  45337  45341  45343  45361  45377  45389  45403
# 45413  45427  45433  45439  45481  45491  45497  45503  45523  45533
# 45541  45553  45557  45569  45587  45589  45599  45613  45631  45641
# 45659  45667  45673  45677  45691  45697  45707  45737  45751  45757
# 45763  45767  45779  45817  45821  45823  45827  45833  45841  45853
# 45863  45869  45887  45893  45943  45949  45953  45959  45971  45979
# 45989  46021  46027  46049  46051  46061  46073  46091  46093  46099
# 46103  46133  46141  46147  46153  46171  46181  46183  46187  46199
# 46219  46229  46237  46261  46271  46273  46279  46301  46307  46309
# 46327  46337