Tekijöihin jako ja alkuluvut¶
(define (tekijä luku jakaja)
(cond
[(= luku 1)
empty]
[(= (modulo luku jakaja) 0)
(cons jakaja (tekijä (/ luku jakaja) 2))]
[else
(tekijä luku (+ jakaja 1))]))
(check-expect (etsi-tekijät 10) (list 2 5))
(check-expect (etsi-tekijät 11) (list 11))
(check-expect (etsi-tekijät 300) (list 2 2 3 5 5))
(define (etsi-tekijät luku)
(tekijä luku 2))
(check-expect (alkuluku? 2) #true)
(check-expect (alkuluku? 3) #true)
(check-expect (alkuluku? 11) #true)
(check-expect (alkuluku? 4) #false)
(check-expect (alkuluku? 15) #false)
(define (alkuluku? luku)
(= (length (etsi-tekijät luku)) 1))
(check-expect (etsi-alkuluvut 0 100) empty)
(check-expect (etsi-alkuluvut 1 2) (list 2))
(check-expect (etsi-alkuluvut 7 2) (list 2 3 5 7 11 13 17))
(check-expect (etsi-alkuluvut 1 15) (list 17))
(define (etsi-alkuluvut kuinka-monta aloitus)
(cond
[(= kuinka-monta 0)
empty]
[(alkuluku? aloitus)
(cons aloitus (etsi-alkuluvut (- kuinka-monta 1) (+ aloitus 1)))]
[else
(etsi-alkuluvut kuinka-monta (+ aloitus 1))]))
Tehtävä vielä
Kommentoitu versio ja vertailu helppolukuisuudesta
Tehtävä vielä
Nopeampi versio, joka tarkistaa vain neliöjuureen asti, ja kolmas joka tarkistaa jakamalla aikaisemmilla alkuluvuilla
Tehtävä vielä
Katsoa wikipediasta oikeasti nopea algoritmi
Tehtävä vielä
Vertailu kertolaskun ja tekijöiden etsimisen nopeudesta: RSA