Nyt olen joutunut opiskelemaan tuota lukuteoriaa ja sen alkeita, ja monet niistä teorioista ovat innoittaneet minulle pieniä Clojure-ohjelmia. Se pää kun on aika tyhjä miettiessäni erilaisia projekteja. Tämä on sitten vaihtoehto, kun Project Euler tai muut vastaavat sivustot eivät innosta.

Kirjoitin siis tehtävää, jossa piti jakaa lukuja alkutekijöihinsä. Luontevin algoritmi oli paperilla tehdessä aloittaa pienimmästä alkuluvusta, kakkosesta. Katsella sitten, jakaako se tämän ison lukumme. Jos jakaakin, niin sitten katsellaan, jakaako , , … sen myös. Sitä rataa kunnes ei jaa, merkitään saatu ylös, ja kokeillaan seuraavaa alkulukua listasta. Aritmetiikan peruslauseen nojalla jossain vaiheessa päädymme tapaukseen, jossa iso lukumme on itsekin alkuluku, eli se on viimeinen tekijöistämme.

Nyt funktionaalisin kielin ilmaistuna tämä on hyvin selvä tapaus, 101-kurssien heiniä. Tätä kuvailemaani algoritmia varten tarvitsemme listan alkuluvuista. En jaksa nyt toteutella mitään seuloja, joten otan listan valmiina:

(ns factoring.core
  (:use [clojure.contrib.lazy-seqs :only [primes]]))

Tästä seuraavasta apufunktiosta lähdin liikkeelle, aitoa bottom-up -meininkiä!

(defn divs?  [a b]
  (= (rem a b) 0))

Sitten se varsinainen pihvi yhdessä komeudessa:

(defn factor
  "Form a canonized presentation of a number: return a vector of primes"
  [number]
  (loop [primes primes, n number, acc []]
    (let [prime (first primes)]
      (if (= 1 n)
        acc
        (if (divs? n prime) ; prime belongs to the presentation
          (recur primes     ; keep the prime there for multiple occures
                 (/ n prime)
                 (conj acc prime))
          (recur (rest primes) ; prime doesn't belong to the pres.
                 n
                 acc))))))

Rekursiivisesti käymme annettua lukua läpi niin, että pienintä ei-kokeiltua alkulukua testaamme jaollisuudella, ja jos ei tärppää, jatkamme seuraavalla alkuluvulla. Jos tärppää, niin lisäämme tämän alkuluvun tekijälistaan ja kokeilemme uudestaan samalla alkuluvulla. Lukua jaamme sitten pienemmäksi kokoajan. Kertymämuuttuja acc kattaa siis tekijät sievässä järjestyksessä. Esimerkkilopputulos olisi vaikkapa (factor 24) = [2 2 2 3]. Koko homma on tässä.

Algoritmin ansiosta alkuluvut ovat kasvavassa järjestyksessä valmiina. Käyttäjiä varten ja omaksi huvituksekseni kirjoitin vielä muotoilijan, joka muistuttaa enemmän kirjoitetussa muodossa esitettyä kanonista muotoa:

(defn format-nicely
  "Return a nice formed string of factors"
  [factorcoll]
  (apply str 
         (interpose "*" 
                    (for [p (partition-by identity factorcoll)]
                      (let [prime (first p)
                                  power (count p)]
                        (if (= 1 power)
                          (str prime)
                          (str prime "^" power)))))))

Tässä interpose ottaa erottimen ja listan argumentteinaan, ja työntää erotinta listan alkioiden väleihin. Tämä erotin tässä on kertomerkki ja lopuksi koko roska käännetään palautettavaksi merkkijonoksi. Hiphei!