Primfaktorisering

Sådan Opdeles et Tal i Dets Primtalsbyggesten

Ethvert helt tal større end 1 kan opdeles i et unikt sæt af primtal ganget sammen — dets primtalsfaktorisering. Indtast et helt tal, og denne beregner finder den faktorisering med det samme, sammen med om tallet selv er et primtal.

Formlen

Aritmetikkens fundamentalsætning garanterer, at hvert helt tal N større end 1 har præcis én primtalsfaktorisering, op til den rækkefølge, faktorerne er skrevet i:

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

hvor hver $\vB{p_i}$ er et distinkt primtal, og hver $\vC{a_i}$ er, hvor mange gange det primtal går op i N uden rest.

Denne beregner finder den faktorisering ved brug af prøvedivision: startende ved 2, tjekker den gentagne gange, om hvert tal går op i det, der er tilbage, uden rest, dividerer det ud (og tæller hvor mange gange), når det gør, og bevæger sig derefter til den næste kandidat. Når en kandidats kvadrat overstiger det, der er tilbage, må alt, der stadig er tilbage, selv være et primtal — enhver mindre faktor ville allerede være fundet:

$$\text{hvis } \vD{d}^2 > \vE{\text{resterende værdi}}, \text{ så er } \vE{\text{resterende værdi}} \text{ et primtal}$$

Eksempel

At finde primtalsfaktoriseringen af 360:

1. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 går op 3 gange; 45 er ulige, så gå videre).
2. 45 ÷ 3 = 15, ÷ 3 = 5 (3 går op 2 gange; 5 er ikke deleligt med 3 igen).
3. 5 er tilbage, og intet yderligere divisorkvadrat er ≤ 5, så 5 er selv et primtal.
4. Resultat: 2³ × 3² × 5.

Vigtige Faktorer At Overveje

• Hver primtalsfaktorisering er unik — dette er præcis, hvad Aritmetikkens fundamentalsætning garanterer. Uanset hvordan et tal opdeles, kommer dets primtalsfaktorisering altid ud den samme (bortset fra rækkefølgen, faktorerne er skrevet i), hvilket er grunden til, at primtalsfaktorisering er en så fundamental byggesten på tværs af talteori.
• Primtalsfaktorisering er mekanismen bag at finde en Største Fælles Faktor eller Mindste Fælles Multiplum i hånden. At sammenligne to tals primtalsfaktoriseringer direkte afslører deres SFF (de delte primfaktorer, ved den lavere delte eksponent) og MFM (hver primfaktor, ved den højere eksponent) — se GCF/LCM-Beregneren for netop den sammenligning.
• At faktorisere store tal bliver beregningsmæssigt meget sværere, efterhånden som antallet af cifre vokser, hvilket er grundlaget for nogle krypteringsmetoder. Prøvedivision (metoden brugt her) fungerer godt for tal, folk typisk indtaster i hånden, men at faktorisere et meget stort tal med hundredvis af cifre kan være beregningsmæssigt uoverkommeligt selv for kraftfulde computere — denne sværhedsgrad er præcis, hvad der ligger til grund for RSA-krypteringens sikkerhed.
• Et primtal har præcis én primfaktor: sig selv, i første potens. Dette er grunden til, at denne beregners “er dette tal et primtal”-tjek falder direkte ud af faktoriseringsprocessen — hvis prøvedivision aldrig finder en faktor mindre end tallets egen kvadratrod, har tallet ingen faktorisering ud over sig selv.

Almindelige Fejl

• At forveksle primtalsfaktorisering med en fuld liste af faktorer. 12’s faktorer er 1, 2, 3, 4, 6 og 12, men dens primtalsfaktorisering er kun 2² × 3 — primtalsfaktorisering beholder kun primbyggestenene, ikke ethvert tal, der går op uden rest.
• At behandle 1 som et primtal. Per definition har et primtal præcis to distinkte divisorer (1 og sig selv) — 1 har kun én, så det er hverken et primtal eller sammensat, og optræder aldrig i en primtalsfaktorisering.
• At miste overblikket over gentagne primfaktorer. 8’s primtalsfaktorisering er 2³, ikke bare “2” — at glemme, hvor mange gange et primtal går op, ændrer det tal, faktoriseringen faktisk repræsenterer.

Godt At Vide

• Har du brug for Største Fælles Faktor eller Mindste Fælles Multiplum af to tal i stedet for ét tals egne faktorer? Største Fælles Divisor og Mindste Fælles Multiplum Beregner sammenligner direkte to tals primtalsfaktoriseringer.
• Forkorter du en brøk til dens laveste form? Brøk Beregner bruger de samme delte primfaktorer, som denne beregner finder.
• Arbejder du i stedet med et meget stort eller meget lille tal? Videnskabelig Notation Beregner konverterer mellem standard- og videnskabelig notation.