Ontbinden in priemfactoren

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de wiskunde heet het ontbinden in priemfactoren, of alleen het ontbinden in factoren, van een geheel getal n, 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, die een deler van n zijn, 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 operatie, die alleen wordt uitgevoerd op de gehele getallen groter dan 1.

Bijvoorbeeld

,

3 maal een 2, 1 maal een 3 en 2 maal 13.

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

Trial division[bewerken]

De trial-division-methode is een eenvoudige maar bewerkelijke methode om een samengesteld getal in priemfactoren te ontbinden. Varianten van dit algoritme kunnen ook gebruikt worden 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 naar een computerterminal schrijft.

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

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

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

$ java TrialDivision 1000 100 2310 101 10 30 900
1000 = 2^3 * 5^3
100 = 2^2 * 5^2
2310 = 2 * 3 * 5 * 7 * 11
101 = 101
10 = 2 * 5
30 = 2 * 3 * 5
900 = 2^2 * 3^2 * 5^2

de priemfactoren van de lijst als argument opgegeven getallen.

TrialDivision.java[bewerken]

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

  1. In de eerste while()-lus wordt, te beginnen bij deler = 2, het kleinste getal opgezocht waardoor het getal n deelbaar is.
  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 terminal geschreven.
  4. Als de nieuwe waarde van n groter is dan 1 dan wordt en een " * "-string naar de terminal geschreven 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 void factoriseer(int n) {
// stap 1
        int deler = 2;
        while (n % deler != 0) deler++;     // kleinste deler opzoeken
// stap 2
        int k = 0;
        while (n % deler == 0) {
             n /= deler;                    // nieuwe waarde van n
             k++;
        }
// stap 3
        if (k == 1) System.out.print(deler);  // waarde van deler
        else System.out.print(deler+"^"+k);   // of deler^k naar de terminal schrijven
// stap 4
        if (n > 1) {
            System.out.print(" * ");        // " * " naar terminal schrijven
            factoriseer(n);                 // naar volgende cyclus
        }                                   // einde van de factorisatie
    }

    public static void main(String[] args) {

        for (int i=0;i<args.length;i++) {     // waarden voor n
            int n = Integer.parseInt(args[i]);
            System.out.print(n+" = ");
            factoriseer(n);
            System.out.println();
        }
    }
}

Zie ook[bewerken]