Prima faktoro
En nombroteorio, la primaj faktoroj de pozitiva entjero estas primoj kiu dividas la entjeron akurate, sen resto. La procezo de trovado de ĉi tiuj nombroj estas entjera faktorigo, aŭ prima faktorigo.
Por prima faktoro p de n, la obleco de p estas la plej granda eksponento a por kiu pa dividas na n.
Du pozitivaj entjeroj estas interprimoj se kaj nur se ili ne havas komunajn primajn faktorojn. La entjero 1 estas interprimo al ĉiu pozitiva entjero, inkluzivante sin. Ĉi tiu estas ĉar ĝi ne havas primajn faktorojn; ĝi estas la malplena produto. Ĉi tio ankaŭ sekvas de difino de a kaj b kiel interprimoj se PGKD(a, b)=1, Tiel PGKD(1, b)=1 por ĉiu b>=1. Eŭklida algoritmo povas esti uzita al difini ĉu du entjeroj estas interprimoj sen scio de iliaj primaj faktoroj; la algoritmo ruliĝas en tempo polinoma de la kvanto de ciferoj.
La prima faktorigo de pozitiva entjero estas listo de la entjeraj primaj faktoroj, kun ankaŭ iliaj oblecoj. La fundamenta teoremo de aritmetiko diras ke ĉiu pozitiva entjero havas la solan priman faktorigon.
Por pozitiva entjero n, la kvanto de primaj faktoroj de n kaj la sumo de la primaj faktoroj de n (ne kalkulante la obleco) estas ekzemploj de aritmetikaj funkcioj de n kiuj estas alsumaj sed ne plene alsumaj.
La funkcio Ω Ω(n) estas la tuteca kvanto de primaj faktoroj de nenegativa entjero n, kalkulante ilin kun oblecoj. La ω(n) estas kvanto de malsamaj primaj faktoroj de n.
Difino de primaj faktoroj de nombro estas ekzemplo de problemo ofte uzata por certiĝi en ĉifrika sekureco en ĉifradaj sistemoj; ĉi tiu problemo estas kredita al postuli pli ol polinoman tempo de la kvanto de ciferoj; estas relative facile al konstrui problemon tiu devus preni pli longa tempon ol la sciata aĝo de la Universo por kalkuli sur aktualaj komputiloj.
Ekzemploj
- La primaj faktoroj de 6 estas 2 kaj 3 (6 = 2 × 3). Ambaŭ havas oblecon 1.
- 5 havas nur unu priman faktoron 5 (5 estas primo). Ĝi havas oblecon 1.
- 100 havas du primajn faktorojn: 2 kaj 5 (100 = 22 × 52). Ambaŭ havas oblecon 2.
- 2, 4, 8, 16, kaj tiel plu ĉiu havas nur unu priman faktoron 2. (2 estas primo, 4 = 22, 8 = 23, kaj tiel plu)
- 1 havas ne primajn faktorojn.
Vidu ankaŭ
Eksteraj ligiloj
greke Javascript prima faktora kalkulilo. Por nombroj supren al proksimume 9×1015 greke Java apleto: Faktorigo uzante la elipsan kurban manierob por trovi faktorojn kun 20+ ciferoj greke Listoj de komponigitaj kun prima faktorigo (unuaj 100, unuaj 1000, unuaj 10000, unuaj 100000, kaj unuaj 1000000).