matematikk.net

Posted: **04/08-2014 23:21**

Hei, det er en liten ting jeg lurer på. Nedenfor er det en kode, jeg skjønner hva koden gjør, men det er noen matematiske ting jeg lurer på.

Code: Select all

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)

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?

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 ?

Håper dere skjønner hva jeg mener :]

Posted: **05/08-2014 01:18**

Zahand wrote: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?

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 wrote: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 ?

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!

Håper dette hjalp.

Posted: **05/08-2014 02:18**

Tusen takk for svaret. Det hjalp veldig

matematikk.net

Eratosthenes' sil i python

Eratosthenes' sil i python

Re: Eratosthenes' sil i python

Re: Eratosthenes' sil i python