Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Kode: Velg alt
def sieve(n):
np1 = n + 1
s = list(range(np1))
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1):
if s[i]:
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
Hvis et tall k ikke er et primtall, så kan det faktoriseres i to faktorer a og b. k = a * b hvis a og b er større en kvadratroten av k, så må a * b være større enn k. Derfor må enten a eller b være mindre enn kvadratroten av k. Derfor, hvis du ønsker å finne en faktor til k, så er det nok å sjekke verdier opp til kvadratroten av k.Zahand skrev:1. For-løkkens grense går fra 2 til "sqrtn + 1". Men hvorfor er det til roten av n + 1 og ikke bare n+1?
i if-testen er s sann hvis i er et primtall. Så ønsker vi å sette alle tall som har i som en faktor til 0. Det laveste SOM IKKE ALLEREDE ER SATT TIL 0 er i*i. Tenk deg at 2 er et primtall. Da må vi sette 2*2=4, 6, 8, osv til 0. 3 er et primtall, da må vi sette 3*3=9, 12,15 osv til 0 men vi trenger ikke sette 6 til 0 fordi det er allerede gjort!Zahand skrev:2. I if-setningen står det "s[i*i:np1:1] = .... " Her bruker det "list slice" (vet ikke hav det heter på norsk, men hvofor starter det fra i*i ?
