Keskustelu: Koodit: Python: Alkulukuja Eratostheneen seulalla

from math import sqrt

# Eratostheneen seula:
# Määritellään raja, jota pienemmät alkuluvut generoidaan
# Eratostheneen seulan avulla, ja palautetaan ne listana.
# Algoritmi on selostettu mm. seuraavilla sivuilla:
# - http://fi.wikipedia.org/w/index.php?title=Eratostheneen_seula&oldid=1660697
# - http://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=78771104

def alkuluvut ( maksimi ):
	"""Palauttaa listana ne alkuluvut, jotka ovat maksimia pienempiä\
	tai yhtä suuri kuin maksimi."""

	# Tarkastetaan, että maksimi on mielekäs
	if maksimi < 2:
		return ""

	#Oletetaan aluksi, että kaikki luvut ovat alkulukuja
	alkuluvut = range ( 2, maksimi + 1 )

	# Poistetaan aina pienimmän jäljellä olevan käsittelemättömän
	# luvun monikerrat kunnes pienin  käsittelemätön luku on pie-
	# nempi tai yhtäsuuri kuin maksimin neliöjuuri. Tämän jälkeen
	# jäljellä ovat vain alkuluvut.
	for i in range(0, int( sqrt( maksimi ) + 1) ):
		for n in range ( 2, maksimi / alkuluvut[i] + 1 ):
			a = alkuluvut[i]*n
			if a in alkuluvut:
				alkuluvut.remove(a)
	return alkuluvut

# tulostetaan alkuluvut, jotka <= 1000
aluvut = alkuluvut(1000)
print aluvut
print "Alkulukuja oli %i kappaletta" % ( len ( aluvut ) )

def aluvut(raja):
    luvut = [1] * (raja + 1)

    for i in range(2, raja ** .5 + 1):
        if luvut[i] == 0:
            continue
        for j in range(i * i, raja + 1, i):
            luvut[j] = 0

    maara = 0

    for i in range(2, raja + 1):
        if luvut[i]:
            # print i,
            maara += 1

    print
    print maara

aluvut(1000000) # 78498

Private Sub Command1_Click()
    Dim NumberTable() As Boolean
    Dim Value As Long, Total As Long
    Dim A As Long, B As Long, C As Long

    'validate given number
    Select Case Val(Text1.Text)
        Case Is < 9
            MsgBox "Please give a number from 9 up to 800000.", vbInformation
            Exit Sub
        Case Is < 800000
            Total = CLng(Text1.Text)
        Case Else
            Total = 800000
            Text1.Text = Total
    End Select

    'reserve memory
    ReDim Preserve NumberTable(Total \ 2)

    'init these
    A = 3
    B = 9
    'look for the non-primes
    Do While B < Total
        'minor optimization (but works so for only the smaller primes)
        C = A + A
        'mark non-primes
        Do While B < Total
            NumberTable(B \ 2) = True
            'to next non-prime
            B = B + C
        Loop
        'prepare for the next prime
        A = A + 2
        'we want only prime numbers, thus...
        Do While NumberTable(A \ 2)
            A = A + 2
        Loop
        'value we start with the next time
        B = A * A
    Loop

    'add to listbox
    List1.Visible = False
    List1.Clear
    List1.List(0) = "2"
    B = 1
    For A = 1 To (Total - 1) \ 2
        If Not NumberTable(A) Then List1.AddItem A + A + 1
    Next A
    List1.ListIndex = 0
    List1.Visible = True
End Sub