Primtalsfaktorisering – kalkylator

Dela upp ett tal i primtal

Varje heltal större än 1 kan skrivas som en produkt av primtal på exakt ett sätt, bortsett från faktorernas ordning. Detta är aritmetikens fundamentalsats, och primtalsfaktoriseringen av ett tal är just den unika produkten. Till exempel är 360 = 2³ × 3² × 5. Den här kalkylatorn hittar faktoriseringen av varje heltal upp till 9,007,199,254,740,991, vilket är 2^53 − 1 och det största heltal som en webbläsare kan representera exakt. Resultaten visas i exponentform, i fullständigt utskriven form och som ett faktorträd.

Delare, deras antal och deras summa

När du känner till primtalsfaktoriseringen följer många andra egenskaper direkt. Om ett tal är lika med p₁^a₁ × p₂^a₂ × … är antalet positiva delare (a₁ + 1)(a₂ + 1)…, eftersom varje delare väljer en exponent från 0 upp till den fulla potensen för varje primtal. Summan av delarna är produkten av (1 + p + p² + … + p^a) över primtalen. För 360 ger det 4 × 3 × 2 = 24 delare med summan 1170. Verktyget listar alla delare i stigande ordning, vilket hjälper vid uppgifter som att hitta gemensamma faktorer, förkorta bråk och kontrollera om ett tal är perfekt, det vill säga om dess delare utom talet självt summerar till talet.

Hur faktoriseringen fungerar

Små primtalsfaktorer tas bort genom provdivision med ett hjul som hoppar över multipler av 2 och 3. Det som återstår har bara stora primtalsfaktorer, så kalkylatorn kontrollerar det med ett deterministiskt Miller-Rabin-test, och om det är sammansatt delas det upp med Pollard's rho-algoritm med exakt BigInt-aritmetik och faktoriseras sedan rekursivt. Det gör att även produkter av två primtal i storleksordningen tiotals miljoner returneras snabbt, där ren provdivision skulle vara långsam. Faktorträdet visar ett sätt att nå primtalen genom att skala av det minsta primtalet i varje steg.

I batchläget kan du klistra in en hel lista med tal och få en tabell med varje faktorisering och antal delare, medan ogiltiga poster markeras var för sig i stället för att stoppa körningen. Allt beräknas i din webbläsare, så de tal du anger laddas aldrig upp.