Ontbinden in priemfactoren

In de wiskunde heet het ontbinden in priemfactoren, of alleen het ontbinden in factoren, van een geheel getal $n$ met $n>1$ het vinden van de delers van $n$, die priemgetallen zijn. Wanneer zij weer met elkaar worden vermenigvuldigd is de uitkomst weer $n$. Voor ieder van de gevonden priemgetallen $p$ kan het voorkomen, dat $p$ het getal $n$ meer dan één keer deelt. De hoofdstelling van de rekenkunde zegt dat, afgezien van de volgorde waarin de priemgetallen worden gevonden, zodat $n$ daar door kan worden gedeeld, steeds dezelfde priemgetallen worden gevonden.

Een priemgetal is per definitie een getal dat niet verder in priemfactoren is te ontbinden. 1 wordt niet meegerekend als priemgetal. Het ontbinden in priemfactoren is een bewerking, die alleen wordt uitgevoerd op de gehele getallen groter dan 1.

Bijvoorbeeld

$4056=2^{3}\times 3\times 13^{2}$,

2 tot de 3e macht maal 3 maal 13 tot de 2e macht = 8 x 3 x 169.

Het ontbinden van een getal in factoren is onderdeel van de getaltheorie.

Methoden

Er zijn verschillende algoritmen om een getal $n$ te ontbinden, zoals de:

• uitprobeermethode
• Pollards p–1-methode
• algoritme van Lenstra
• Dixons factorisatiemethode

Uitprobeermethode

De uitprobeermethodemethode, vaak met het Engelse trial division aangegeven, is een eenvoudige maar bewerkelijke methode om een samengesteld getal in priemfactoren te ontbinden. Varianten van dit algoritme kunnen ook worden gebruikt om de elementen van een eindige deelverzameling van de priemgetallen te berekenen.

Hieronder staat ter illustratie de Java-code van een inefficiënt, recursief algoritme dat de gevonden priemfactoren tijdens het factorisatieproces aan een string toevoegt en het resultaat na de ontbinding naar een computerterminal schrijft.

De factorisatie wordt door de functie factoriseer(n) uitgevoerd. Samengevat wordt tijdens elke cyclus de volgende bewerking:

factoriseer(n) -> deler^k * factoriseer(n / deler^k)

uitgevoerd, waarbij de waarde van deler^k naar de string wordt geschreven. Na compilatie van TrialDivision.java geeft de opdracht:

$ java TrialDivision  1000 100 51 101 2310 3599
1000 = 2^3 * 5^3
100 = 2^2 * 5^2
51 = 3 * 17
101 = 101
2310 = 2 * 3 * 5 * 7 * 11
3599 = 59 * 61

de priemfactoren van de als argument opgegeven lijst getallen.

TrialDivision.java

In factoriseer(n) zijn de volgende stappen te onderscheiden:

1. In de eerste while()-lus wordt, te beginnen bij deler = 2, de kleinste deler van n opgezocht.
2. Vervolgens wordt het getal n in de tweede while()-lus k-maal door de waarde van deler gedeeld.
3. De waarde van deler of deler^k wordt naar de string geschreven.
4. Als de nieuwe waarde van n groter is dan 1 dan wordt en een " * "-string toegevoegd en wordt n verder ontbonden. Als n de waarde 1 heeft bereikt dan wordt de factorisatie gestopt.

Gewoonlijk worden voor de trial-and-error waarden van delers niet alle natuurlijke getallen gebruikt maar alleen de priemgetallen uit een op een efficiënte manier gezeefde verzameling.

public class TrialDivision {

    public static String factoriseer(int n) {
// stap 1
        int deler = 2;
        while (n % deler != 0) deler++;                  // kleinste deler van n opzoeken
// stap 2
        int k = 0;
        while (n % deler == 0) {
             n /= deler;                                 // nieuwe waarde van n
             k++;                                        // bepalen na k maal delen
        }
// stap 3
        String s = "" + deler;                           // waarde van deler
        if (k > 1) s += "^"+k;                           // en ^k aan de string toevoegen
// stap 4
        if (n > 1) s += " * " + factoriseer(n);          // voeg " * " en volgende stap aan string toe
        return s;                                        // string met ontbinding terugsturen
    }

    public static void main(String[] args) {

        for (int i=0;i<args.length;i++) {                // argumenten met de waarden voor n
            int n = Integer.parseInt(args[i]);
            System.out.println(n+" = "+factoriseer(n));  // resultaat van ontbinding naar terminal schrijven
        }
    }
}

Voetnoten