Eratoszthenész szitája - Python

Mivel a product = product+base a belső while cikluson belül van, ezért a candidatesből a külső ciklus első menetében eltávolítjuk candidates.remove(product) a 2, 4, 6, ... számokat. A következő mentben a candidates lista első elemével, a 3-mal játszuk el ugyanezt 3, 6, 9, ... stb.

Ez prímszám rosta.

A legegyszerűbb ha úgy fogod fel, mintha egy számegyenesen előszőr kihúzkodod a 2 többszöröseit (0-tól kezdve minden második számot), majd a 3-ét (0-tól kezdve minden harmadikat), 4-ét stb. Ami a végén marad, az az n. szám alatti prím számok. Ennyi.

Azért prímek maradnak, mert ugye a többszörösök ki vannak húzva, vagyis nincs alatta osztója (csak 1 és önmaga).

(en meg angolrol :) )
Na, szoval, hol kezdjuk?
Mennyire ertesz a programozashoz? Gondolom, ha atirom c++-ba, nem nyersz vele sokat.
Illetve a matekhoz? Kell-e a szita mukodeset taglalnom, vagy eleg, h a elmondom, mi mire jo?
ket listabol indul, az egyiken gyujti a primszamokat (result), a masikon a szamok vannak 3-1000ig, ezek kozul rostalja ki az osszetetteket (candidates). a base valtozoba teszi azt a primszamot, amit az iment talalt, majd a while ciklussal egyesevel minden tobbszoroset kiveszi a listabol (candidates.s.remove(product)). ha 1000ig kivette az osszes tobbszorost, akkor uj erteket ad a base-nek, a candidates lista legkisebb elemet (valojaban a legelsot, de nagysag szerint rendezve vannak). Es ezt ismetelgeti, mig a candidates lista el nem fogy. Ha elfogyott, meg belevagja az utolso primszamot, majd print a kepernyore.
Nem reszleteztem ki a leirast, ha ugy gondolod szukseges, szolj.

Mikor elkezdtem, meg senki sem szolt hozza, most meg a 3ik vagyok :(

Szia Peti!

Én nem ismerem a python-t, de szerintem így működik:

Hát most törlés folyamatát nem ismered vagy a while ciklusok működését?
A törlés menetéről nem kell agyalnod, azt már valaki kitalálta, hogyan kell megoldani. Azért használja a progi a candidates osztály remove() függvényét, mert ott már készen van a lehetőség a törlésre. Annak technikai részleteivel már neked nem kell törődnöd.
Ugyanígy az append() függvény hozzáad egy számot a result (eredmény) osztályhoz. Ez sem lényeges, hogy működik. Ezeket a készen kapott függvényeket csak használjuk. Feltételezzük, hogy jól meg vannak írva.

A while ciklusoknál pedig célszerű a megértést a belső ciklussal kezdeni:

while product < 1000:
if product in candidates:
candidates.remove(product)
product = product+base

Ez egy elől tesztelős ciklus. Megnézi a feltételt, hogy az éppen aktuális product változó kisebb-e mint ezer, ha igen végrehajtja a ciklus belső részét. A ciklus belső pedig abból áll, hogy megnézzük, hogy ez a szám benne van-e még a lehetséges jelöltek (candidates) között. Ha igen, akkor kivesszük a jelöltek közül a remove() függvény segítségével, mert az azt jelenti, hogy azt most megvizsgáltuk, és kiderült róla hogy nem prím. Ezért aztán eltávolítjuk a jelöltek közül.
Történik egy nagyon fontos mozzanat még a ciklus belsejében: növeljük a ciklusváltozó értékét a base értékkel, Így a ciklus változó folyamatosan emelkedő értéket mutat 1000-ig. Pl. ha base=2, akkor 2,4,8,10...996,998. Itt szeretném megjegyezni, hogy véleményem szerint az algoritmus hibás, mert az 1000-et nem tudja kivenni a candidatas halmazból, hiszen mindig csak az 1000-nél kisebb számokat vizsgálja, tehát amikor a product átvált 1000-re, akkor a ciklusmag már nem hajtódik végre, ezért az 1000 nem is lesz kitörölve a halmazból. Tehát a ciklusfeltételnek a (product <= 1000) jobb lenne.

Ezután jön a külső ciklus:

while candidates:

belső cikus (ezt már értjük)

result.append(base)
base = candidates[0]
product = base
del candidates[0]

Ha megvizsgáltunk egy base számot a belső ciklusban, folytatjuk a következő prím számmal és azt is végig végighajtjuk a belső cikluson.
Az előzőleg vizsgált prím számot betesszük az eredmények közzé az append() - hozzáadás függvénnyel. A következő prím pedig az lesz, ami a jelöltek közzül most a legelső. Ezt jelenti a base=candidates[0] kifejezés. A product értéket újra beállítjuk a base kezdeti értékre, és a del (törlés) paranccsal töröljük a jelölt listából a most talált prímet. (Szerintem ez felesleges, mert a belső ciklusban úgyis törlődne). Amikor ez megvan, akkor újra végrehajtjuk a belső ciklust, amíg van jelölt. (while candidates)

(Az én véleményem az, hogy a jelöltek közzé bekerül az 1000 is. Tehát szerintem nem jó a progi.)

Közben még gondolkodtam a dolgon és még valami apróságot hozzáfűznék a hosszú magyarázatomhoz.
Ezt írtam:

A product értéket újra beállítjuk a base kezdeti értékre, és a del (törlés) paranccsal töröljük a jelölt listából a most talált prímet. (Szerintem ez felesleges, mert a belső ciklusban úgyis törlődne).

Utána gondolva nem is tűnik feleslegesnek az a törlés, mert ha bele gondolunk mi történne abban az esetben, amikor a jelöltek halmaza már csak egy elemet tartalmaz, akkor enélkül a törlés nélkül a külső while ciklus újra végrehajtódna, mert a candidates még nem üres. Ez persze magával vonná, hogy a belső ciklusban mégiscsak törlődne ez az utolsó elem, és akkor egy üres halmaz állna elő, aminek még candidates[0] eleme sincs. Ekkor a program valószínűleg index túlcsordulással leállna a

base = candidates[0]

parancsnál.

Tehát módosítom az álláspontomat a del parancs szükséges.

Még valami!
Én így írtam volna meg a programot:

result = [1]
candidates = range(2,1000)
while candidates:
    base = candidates[0]
    result.append(base)
    product = base
    while product < 1000:
        if product in candidates:
            candidates.remove(product)
        product = product+base
result.append(base)
print result

És ekkor az elsőre fölöslegesnek tűnő del most már tényleg nem kell. Ebben kihasználnánk a belső ciklus törlési műveletét is.

Bocs! Sőt:

candidates = range(1,1000)
while candidates:
    base = candidates[0]
    result.append(base)
    product = base
    while product < 1000:
        if product in candidates:
            candidates.remove(product)
        product = product+base
result.append(base)
print result

Ugyan már jól lerágtátok, de imhol az én megoldásom jó régről. Amikor még bencsmarkoltam vele...

#!/usr/bin/python

from time import *

primes = [ 3, 5, 7 ]

def findprimes ():
  for i in xrange( 9, 50000, 2 ):
    for j in primes:
      if i % j == 0:
        break;
    else:
      primes.append ( i )

clock()
findprimes()
print "time: "+ str ( clock()) +" secs, count: "+ str ( len ( primes ))