<< | #470 ; Stulta (sed utila) artikolo pri primoj |
>> |
Ĉi tio artikolo estas iom stulta, sed la intenco tamen estas bona. Temas pri relative malgrandaj entjeroj, simplaj algoritmoj kaj malgrandaj primoj. Nek algoritmoj nek primoj estas stultaj. Ĉi tioj algoritmoj tamen estas uzeblaj nur por tre malgrandaj primoj. Oni ja uzas grandaj (probablaj) primoj ekzemple en kelkaj kriptaĵoj, sed la unuaj primoj estas multe tro malgrandaj por tiaj celoj.
Kio do estas primo? Primo estas pozitiva entjero p
kion oni povas dividi (egale) nur per la unuo (1) aŭ per si mem (p). Mi celas la entjeran dividon. Ni nun uzu la signon / nur por la entjera divido. Do neniaj decimaloj en la rezulto. Ni diras ke la entjera divido a / b = c
ne produktas dividan restaĵon kiam b * c = a
aŭ oni povus diri ke la divida restaĵo estas nulo (0). Kelkaj ekzemploj:
4 / 2 = 2 kaj la divida restaĵo 0 ĉar egalas ja 2 * 2 + 0 = 4 5 / 2 = 2 kaj la divida restaĵo 1 ĉar egalas ja 2 * 2 + 1 = 5 6 / 2 = 3 kaj la divida restaĵo 0 ĉar egalas ja 3 * 2 + 0 = 6
La unuaj primoj estas 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
Ekzemple la entjeroj 9, 15, 21, 25 kaj 27 ne estas primoj ĉar estas 9 = 3 * 3 ; 15 = 3 * 5 ; 21 = 3 * 7 ; 25 = 5 * 5 ; 27 = 3 * 9 = 3 * 3 * 3
kaj ili do havas aliaj dividantoj ol 1 kaj la numero mem.
Antaŭe oni skribis longaj listoj pri primoj. Ekzemple la angla matematika manlibro "CRC Standard Matematical Tables" el jaro 1974 ankoraŭ prezentis primojn ĝis 100000. Elektronikaj kalkuliloj kaj komputiloj tamen tute aliigis la situacion. Oni ne plu eldonas librojn kun multe da primoj, ĉar en la moderna tempo estas facile por ilin kalkuli kaj primoj povas esti kiel grandaj ajn. Ekzistas senfina nombro da primoj. Ĉiam eblas trovi primon kio estas pli granda ol kio ajn numero.
Ni vidas en la parta listo de malgrandaj primoj ekzemple la plej malgrandan primon 20359 kaj la plej grandan 21841. Ĝenerale oni povas prezenti pozitivajn numerojn kiel produto de primfaktoroj kiuj estas primoj. Ekzemple 1000 = 2 * 500 = 2 * 5 * 100 = 2 * 5 * 2 * 50 = 2 * 5 * 2 * 5 * 10 = 2 * 5 * 2 * 5 * 2 * 5
, sed primojn ne eblas partigi same.
Ni povus produkti el du primoj iom grandan numeron, ekzemple 20359 * 21841 = 444660919
kaj klare la produto ne estas primo, ĉar havas la du primojn kiel primfaktoroj, sed tio ne estas tre facile por pruvi per mana kalkulado.
Ni demandu kelkaj stultaj demandoj. Demandoj estas utilaj, eĉ tiel nomitaj stultaj demandoj. Ĉu la numero 1 estas primo? Ne, ĉar estas la unuo. Ĉiuj primoj estas pli grandaj.
Estas facile por kompreni ke paraj numeroj ĝenerale ne estas primoj, ĉar ili ja estas (egale) divideblaj per la numero 2. Se estas entjero x > 1
ni povas diri ke por la para numero x * 2
validas (x * 2) / 2 = x
kaj sen divida restaĵo kaj do la para numero x * 2
ne estas primo. Kial la plej malgranda para numero 2 do estas primo? Nu, ĝi ja plenumas la difinon de primo, (egale) dividebla nur per 1 kaj per si mem. La numero 2 do estas la sola para primo.
2 / 1 = 2 kaj la divida restaĵo 0 ĉar egalas ja 1 * 2 + 0 = 2 2 / 2 = 1 kaj la divida restaĵo 0 ĉar egalas ja 2 * 1 + 0 = 2
Pli facile estas por kalkuli rekte la dividan restaĵon de entjera divido. Ni uzu la simbolon % por la divida restaĵo. La dividanto b
dividas la numeron a
en la entjera divido se la divida restaĵo egalas nulo ; a % b = 0
.
10 % 2 = 0 ĉar egalas 2 * 5 + 0 = 10 10 % 5 = 0 ĉar egalas 5 * 2 + 0 = 10 49 % 7 = 0 kaj 7 do dividas la numeron 49 50 % 3 = 2 kaj 3 do ne estas faktoro de 50 p / 1 = p la unuo dividas ĉiujn numerojn p / p = 1 la numero mem dividas ĉiujn numerojn p % 1 = 0 p % p = 0 la divida restaĵo de entjera divido = 0
Kiel oni do trovas la primojn, pli grandajn ol la unuajn, ekzemple 2 kaj 3? Kiel oni testas ĉu io entjera numero estas primo? Estas ja facile por kompreni ke ĉiuj paraj numeroj pli grandaj ol 2 ne povas esti primoj. Same ni povas diri ke trioblaj numeroj (6, 9, 12, 15, 18, ...) pli grandaj ol 3 ne povas esti primoj, ĉar ili estas ja divideblaj per 3.
Tre simpla, stulta kaj neefekta testo por (malgranda) entjera numero t >= 3
, ĉu estas primo? Oni provu dividi la numeron t per ĉiuj entjeraj dividantoj d >= 2
kioj estas pli malgrandaj ol t, do estas 1 < d < t
. Se la divida restaĵo por io dividanto d estas nulo, la numero t ne estas primo. Se nenio divida restaĵo estas nulo, estas la numero t primo.
Ni ja ne bezonas testi entjeran dividon per dividantoj kioj estas pli grandaj ol la numero t kion ni testas. Ili ja ne povas esti faktoroj de testata numero. Fakte ni povas fini la teston jam antaŭe. Se la kvadrato de dividanto d * d
estas pli granda ol la testata numero t, tiam oni ne plu bezonas testi la dividanton d. Kaj certe ni scias ke ĉiuj paraj numeroj pli grandaj ol 2 ne povas esti primoj. Se ni jam testis per dividanto d = 2
kaj konstatis ke ĝi ne dividas la numeron t, ne plu valoras testi per aliaj paraj dividantoj kiel 4, 6, 8, 10, ... Pli bone oni testu per la unuaj primoj 2 kaj 3 kaj poste nur per neparaj dividantoj 5, 7, 9, 11, 13, ...
Eblas iom plibonigi la metodon. Ekzemple estas pli efekte por testi nur per malgrandaj primoj kioj estas pli malgrandaj ol la kvadrata radiko de numero t ... aŭ egale grandaj. Se la kvadrato de dividanto jam estas pli granda ol la testata numero ( d * d > t
) estas la rezulto jam klara se ni testis la dividantojn en ordo.
Mi volas disvolvi propran simbolan esperantan programan pseŭdolingvon por esprimi la algoritmojn pli klare. Nenio komputilo komprenas la pseŭdolingvon, estas nur por homoj. Jen unue la funkcio por kalkuli ĉu la entjero numero
(numero > 3) estas primo? La plej simpla vario. La nova signo % signifu la restaĵon de entjeran divido. Se ekzemple validas a % b = 1
tiam egalas en entjera divido a / b = c + 1
FUNKCIO ĉuEstasPrimo ( numero ) METU rezulto = JES FARU dividanto = 2 ĜIS (numero - 1) PAŜO +1 SE ESTAS numero % dividanto == 0 METU rezulto = NEE EKSTEREN SE FINO FARU FINO FUNKCIO FINO
Espereble la enhavo de funkcio estas sufiĉe bone komprenebla. Unue ni simple supozas ke la numero estas primo ( METU rezulto = JES
). Se ni trovas ke la numero tamen estas dividebla per io dividanto kio estas alia ol 1 kaj alia ol la numero mem, ni konkludas ke la numero ne estas primo ( METU rezulto = NEE
) kaj oni ne bezonas esplori la aferon pli multe.
Ni donas en "lopo" por la dividanto
sinsekvaj valuoj 2, 3, 4, 5, ... ĝis kiam la valoro estas pli malgranda ol la testa numero. Ni ne volas dividi la numeron per la numero mem ĉar tia divido ĉiam produktus entjeran restaĵon 0, kaj por kelkaj kazoj tio estus falsa rezulto. Ni testas ĉiujn la dividantojn per entjera divido ( SE ESTAS numero % dividanto == 0
) kaj se ni ne trovas nulon kiel entjera restaĵo, ni provizore supozu ke la numero estas primo ... se oni poste ne trovas alian rezulton.
Ni ja ne provas trovi ĉiujn la faktorojn de numero. Jam la unua kazo numero % dividanto == 0
pruvas ke la numero ne estas primo kaj plua testado ne povas aliigi la rezulton. Ni testas la dividantojn en ordo kaj tial ni provas trovi la plej malgrandan dividanton kio dividas la numeron, la plej malgrandan faktoron de numero. Ni finu kaj forlasu la teston tuj se ni trovas dividanton.
Ni plenumu "tablan teston" por la algoritmo. Estu la testata numero == 5
. Unue estas dividanto = 2
kaj estas ja 5 % 2 = 1 ĉar 5 = 2*2 + 1. Tial ni kontinuas kun la pli granda valuo dividanto == 3
kaj kalkulas 5 % 3 = 2 ĉar 5 = 1*3 + 2. Ni fine ankoraŭ provas valuon dividanto == 4
kaj kalkulas 5 % 4 = 1 ĉar 5 = 1*4 + 1. Nenio valuo dividanto < numero
do ne produktis la entjeran restaĵon nulo (0) kaj tial la komenca supoza valuo estas la fina rezulto, 5 estas primo.
Alia ekzemplo. Estu la testata valuo numero == 1234
. En komenco ni supozas ke estas primo, sed jam la unua entjera divido egalas 1234 % 2 = 0 ĉar 1234 = 2*617 + 0. Tial ni povas tuj decidi ke la numero 1234 ne estas primo ( METU rezulto = NEE
) kaj ni ne bezonas testi pli grandaj dividantoj. La komando EKSTEREN kaŭzas ke la lopo finiĝas.
La supra algoritmo ja estas neefekta por pli grandaj numeroj ĉar ĝi testas multe da dividantoj kioj ne povas esti primoj kaj kioj ne povas esti primfaktoroj de testata numero. Pli bone estus por testi nur dividanton 2 kaj sekve la neparajn dividantojn 3, 5, 7, 9, 11, ... tiom ke la kvadrato de dividanto ankoraŭ estas pli malgranda ol la testata numero ... aŭ egala al la numero. Nun tamen prefere estu la testa numero >= 4
. Nova pli bona vario de algoritmo:
FUNKCIO ĉuEstasPrimo ( numero ) METU rezulto = JES METU dividanto = 2 METU kvadrato = dividanto * dividanto RIPETU KIAM kvadrato <= numero SE ESTAS numero % dividanto == 0 METU rezulto = NEE EKSTEREN SE FINO SE ESTAS dividanto == 2 METU dividanto = dividanto + 1 CETERE METU dividanto = dividanto + 2 SE FINO METU kvadrato = dividanto * dividanto RIPETU FINO FUNKCIO FINO
En la nova algoritmo ni ripetas en la programa lopo tiom longe kiam la kvadrato de dividanto estas pli malgranda ol la testa numero (kaj ni ne trovis ke la dividanto dividas la numeron sen divida restaĵo) ... aŭ egala al la testa numero. La dividanto uzas la valorojn 2, 3, 5, 7, 9, 11, ... ĉar la aliaj paraj dividantoj 4, 6, 8, 10, ... ne estas utilaj.
Ni testu kun la valoro numero == 11
. Unue estas kvadrato = 2 * 2 = 4
kio ja estas pli malgranda ol 11 kaj tial la lopo komencas. Ni konstatas ke egalas 11 % 2 = 1 ĉar 11 = 2*5 + 1 kaj la supoza valuo rezulto == JES
ne aliiĝas. Sekve estos por la dua fojo en la lopo la nova dividanto == 3
kaj kvadrato = 3 * 3 = 9
.
Por la dua rondo en la lopo validas kvadrato <= numero
ĉar estas ja 9 < 11
. Ni kalkulas 11 % 3 = 2 ĉar 11 = 3*3 + 2. La supoza rezulto do ne aliiĝas. Nova valoro por la sekvanta rondo estus dividanto == 5
sed la kvadrato de nova dividanto estos kvadrato = 5 * 5 = 25
kio estas pli granda ol 11 kaj tial la lopo ne plu ripetas, ĉar tute ne eblas ke 5 estus la plej malgranda primfaktoro de 11. Tial la fina rezulto estas la komenca supoza valoro rezulto == JES
; do la numero 11 estas primo.
Mi devis poste iom korektigi la programon. Unue mi pensis ke suficas testi nur RIPETU KIAM kvadrato < numero ...
sed poste mi komprenis ke devas esti RIPETU KIAM kvadrato <= numero ...
. Ni devas testi la dividon ankaŭ tiam kiam la kvadrato de dividanto estas egala al la testata numero. Ni pensu ekzemple la numeron 25. En la komenco la programo supozas ke la numero estas primo, se oni ne povas ĝin dividi. La unuaj dividantoj 2 kaj 3 ne dividas la numeron 25, sed klare 25 ne estas primo. Por la dividanto 5 estus la kvadrato de dividanto 25, egala al la testata numero, sed ni tamen devas provi la dividon por trovi la gravan rezulton 25 % 5 = 0 kio pruvas ke 25 ne estas primo.
Pli prudente eble estus por uzi la pli malgrandajn primojn 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
ĝis la kvadrata radiko de testata numero por testi ĉu la numero estas primo. Ekzemple la dividantoj 9, 15, 21, 25, 27
estas neutilaj kvankam estas neparaj. Testoj per dividantoj 3, 5, 7
jam plenumis la saman laboron.
Se ni havas tabelon de malgrandaj primoj, eblas efekte testi ĉu numero estas primo, se la testata numero estas pli malgranda ol aŭ egala al la kvadrato de plej granda primo en la tabelo. Ni skribu algoritmon por testi entjeron proksimume en intervalo 3 < numero < 10000
.
FUNKCIO ĉuEstasPrimo ( numero ) METU primoj = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 ] SE ESTAS numero > primoj[LONGO DE TABELO primoj] * primoj[LONGO DE TABELO primoj] ERARO EKSTEREN SE FINO METU i = 1 METU rezulto = JES METU kvadrato = primoj[i] * primoj[i] RIPETU KIAM kvadrato <= numero dividanto = primoj[i] SE ESTAS numero % dividanto == 0 METU rezulto = NEE EKSTEREN SE FINO METU i = i + 1 SE ESTAS i > LONGO DE TABELO primoj ERARO EKSTEREN SE FINO METU kvadrato = primoj[i] * primoj[i] RIPETU FINO FUNKCIO FINO
Unue la valuo por la dividanto estas la unua primo en la tabelo primoj, do dividanto = primoj[1] = 2
kaj estas la kvadrato de dividanto kvadrato = primoj[1] * primoj[1] = 2 * 2 = 4
Estas grave ke la programoj kapablu pruvi ke ekzemple la numeroj 7*7 = 49, 11*11 = 121, 13*13 = 169, 17*17 = 289, 19*19 = 361, 23*23 = 529, ... ktp.
- la kvadratoj de primoj - ne estas primoj. Tial la dividanto nepre devas atingi la valoron kio estas egala al la kvadrata radiko de testata numero, se estas entjero.
Se ni trovas primon kio dividas la numeron ( SE ESTAS numero % dividanto == 0
), estas la testa numero ne primo, same kiel antaŭe. Nun ni tamen testas nur per la primoj en la tabelo. La varianto i
indikas la vicmontran numeron de primo en la tabelo. La nombro da primoj en la tabelo estas la valuo "LONGO DE TABELO primoj". Estas limigita nombro da primoj en la tabelo kaj tial ni prefere pensu pri eblaj eraroj pro nekorekta uzo de funkcio. Ni ne volas ke la programo donu falsan respondon.
La uzeblecoj de supra programo klare estas limigitaj por numeroj kioj estas proksimume nur 10000, kio ne estas tre granda numero. Granda ideo tamen estas ke tiom eblas fari kun primoj kioj estas proksimume nur 100 en grando. Ni ja ĉiam komencas testi el la plej malgrandaj eblaj faktoroj (2, 3, 5, ...) kaj tial ni serĉas la plej malgrandan faktoron. Se ni havus en la programo primoj al proksimume la grando 1000, tia programo povus testi primojn ĝis proksimume la grando de miliono. Nome la plej malgranda faktoro por entjero kio ne estas primo, estas maksimume la kvadrata radiko de tio entjero. Se eĉ la kvadrata radiko ne dividas la entjeron, estas la entjero primo. Tial ne estas necese por testi pli grandajn faktorojn por testi ĉu la numero estas primo aŭ ne.
Kiel oni simple trovu la sekvantan primon kio estas iom pli granda ol io pozitiva entjera numero?
FUNKCIO sekvantaPrimo ( numero ) METU provo = numero + 1 RIPETU ĉuPrimo = ĉuEstasPrimo ( provo ) SE ESTAS ĉuPrimo == JES METU rezulto = provo EKSTEREN SE FINO METU provo = provo + 1 RIPETU FINO FUNKCIO FINO
Ni testas en lopo sinsekvajn entjerojn kioj estas pli grandaj ol la donita numero. Ni uzas la funkcion ĉuEstasPrimo
kiel helpilo. Se ni trovas primon, la provita entjero provo
estas la sekvanta primo kaj la tasko de funkcio estas plenumita.
|
Nu fakte la eblaj primoj ne estas sinsekvaj numeroj kaj tial la funkcio ne estas kiel eble plej efekta. Escepte de la du unuaj primoj 2 kaj 3 estas la eblaj primoj de formo 6*n±1
, kie la varianto n estas entjero, n >= 1
. Ĉiuj la laŭ ĉi tio regulo eblaj primoj ne estas vere primoj. Tamen post la unuaj du primoj 2 kaj 3 ne ekzistas primoj por kiuj la regulo ne validas.
Ekzemple por la unua valuo n == 1
la regulo produktas du eblaj primoj 6*n-1 = 6-1 = 5
kaj 6*n+1 = 6+1 = 7
kioj fakte estas la tria kaj la kvara primo. Por la valuo n == 4
la regulo produktas du eblaj primoj 6*n-1 = 24-1 = 23
kaj 6*n+1 = 24+1 = 25
sed la dua rezulto 25 ja ne estas primo ĉar estas 25 = 5*5
. Por la valuo n == 8
la regulo produktas du eblaj primoj 6*n-1 = 48-1 = 47
kaj 6*n+1 = 48+1 = 49
sed la dua rezulto 49 ja ne estas primo ĉar estas 49 = 7*7
.
Oni tamen povas uzi la regulon por iom rapidi la kalkuladon de primoj. Post la komenco en grupo de 30 sinsekvaj numeroj estas 10 eblaj primoj kaj 15 neparaj numeroj. Tial estas pli rapide por uzi la eblajn primojn ol uzi la neparajn numerojn. La veraj primoj ja estus la plej bona alternativo, sed kredeble ne ekzistas tia simpla regulo kio rakontus kun certeco kioj numeroj estas veraj primoj kaj kioj ne estas primoj. Ni apenaŭ povus memorteni ĉiujn la primojn en memoro, ĉar ekzistas ja kiel multe ajn da ili. La simpla regulo por eblaj primoj, 6*n±1
neniam malsukcesas. Ĉiuj eblaj primoj ne estas vere primoj, sed la simpla regulo trovas ĉiujn la eblajn primojn kaj ne perdas primojn.
Malgrandaj primoj estas facilaj por kalkuli, sed pli grandaj veraj primoj estas malfacilaj. Ofte komputila programa lingvo tute ne povas uzi entjerojn kioj estas pli grandaj ol ekzemple 232 = 4294967296 kaj tio entjero fakte ankoraŭ ne estas tre granda numero, nur kelkaj miliardoj. Se pli grandaj entjeroj estas uzeblaj, povas la funkciado de programo tamen esti malrapida.
Grandaj probablaj primoj estas relative facilaj por trovi, sed oni ne povas scii kun absoluta certeco ĉu ili vere estas primoj. Ofte tamen sufiĉas se oni povas fidi ke la primfaktoroj de numero estas iom grandaj, kvankam la numero mem eble ne estas primo. Ekzemple la entjero 99991 * 99989 * 99971 * 99961 = 99 912 025 897 064 911 969
konsistas el kvar iom grandaj primfaktoroj. La entjero estas proksimume 9,99120259 * 1019 kaj ĝi do enhavas 20 cifroj. Mia simpla kalkulilo tamen kapablas montri nur la 8 / 9 unuajn cifrojn kaj la fino de entjero estas neakurata. Klare la produto de kvar primoj ne estas primo, sed estus iom malfacile por trovi la faktorojn ĉar ili estas relative grandaj. Vere grandaj primoj enhavas minimume centoj da numeroj.
Jes, malgrandaj primoj eble ne tre utilaj en praktiko, sed la algoritmoj tamen estas utilaj por kompreni. Estas surprize multe por batali kun relative simplaj aferoj, ekzemple kun primoj.
Kaj certe fine ..........
NI VENKOS!
La Ambasadoro en Finnlando de sendependa nacio Mueleja Insulo |