Kontrollues i numrave të thjeshtë

Si ta përdorësh kontrolluesin e numrave të thjeshtë

1. Shkruaj një Numër i plotë. Pranohen edhe shprehje: 2^61-1, 10^12+39, 20!+1 ose 3711.
2. Përgjigjja shfaqet ndërkohë që shkruan; shtyp Kontrollo që faktorizimit t’i japësh më shumë kohë te një numër i vështirë.
3. Lexo përfundimin, Faktorizimi në numra të thjeshtë, Numri i pjesëtuesve, Numri i thjeshtë paraprak dhe Numri i thjeshtë pasardhës. Paneli Pse shpjegon si u arrit te përgjigjja, ndërsa Kopjo faktorizimin kopjon prodhimin e numrave të thjeshtë.
4. Për të listuar numra të thjeshtë, plotëso Nga dhe Deri te Numrat e thjeshtë në një interval dhe shtyp Listo numrat e thjeshtë.

Pranohen numra deri në 2048 bite (rreth 617 shifra), dhe gjithçka funksionon në shfletuesin tënd.

Çfarë e bën një numër të thjeshtë

Numër i thjeshtë është një numër i plotë më i madh se 1 që ka vetëm dy pjesëtues: 1 dhe vetveten: 2, 3, 5, 7, 11, 13… Një numër me pjesëtues të tjerë është i përbërë dhe mund të shkruhet në një mënyrë të vetme si prodhim numrash të thjeshtë, faktorizimi i tij në numra të thjeshtë (360 = 2³ × 3² × 5). Numrat 0 dhe 1 nuk janë as të thjeshtë, as të përbërë, dhe 2 është i vetmi numër i thjeshtë çift.

Numri i pjesëtuesve rrjedh nga faktorizimi: shto 1 te çdo eksponent dhe shumëzo. 360 = 2³ × 3² × 5 ka (3 + 1)(2 + 1)(1 + 1) = 24 pjesëtues. Një numër i thjeshtë ka gjithmonë saktësisht 2.

Si funksionon testi

• Numrat e vegjël (nën një milion) kontrollohen me pjesëtim provë: nëse asnjë numër i thjeshtë deri te rrënja katrore nuk e pjesëton numrin, ai është i thjeshtë. Nuk ka nevojë të vazhdohet më tej, sepse një numër i përbërë ka gjithmonë një faktor jo më të madh se rrënja e tij katrore.
• Numrat më të mëdhenj pjesëtohen së pari me çdo numër të thjeshtë nën 1000, pastaj kalojnë në testin Miller–Rabin. Me 13 bazat 2, 3, 5, …, 41, ky test është provuar i saktë për çdo numër nën 3,3 × 10²⁴, ku hyjnë të gjithë numrat e plotë 64-bitësh. Për këta numra përgjigjja është e sigurt.
• Mbi 3,3 × 10²⁴ përdoren 25 baza dhe një numër që i kalon të gjitha raportohet si numër i thjeshtë i mundshëm. Gjasa e gabimit është nën 1 në 10¹⁵, por nuk është provë matematikore. Kur testi dështon, numri është i përbërë me siguri.

Si faktorizohen numrat

Faktorët e vegjël gjenden me pjesëtim provë. Pjesët e përbëra më të mëdha ndahen me algoritmin rho të Pollardit (varianti i Brentit), që gjen faktorë deri në rreth 10 shifra brenda një pjese të sekondës. Numrat më të vështirë, si prodhimi i dy numrave të thjeshtë me 15 shifra ose më shumë, mund të kërkojnë shumë më tepër se çdo kufi kohe, ndaj faktorizimi ndalet pas disa sekondash. Faktori i fundit shënohet atëherë si i përbërë por i pandarë, dhe shtypja e Kontrollo edhe një herë i jep më shumë kohë.

Numrat e thjeshtë në një interval

Lista e intervalit përdor një site të Eratostenit të segmentuar, që kryqëzon shumëfishat e çdo numri të thjeshtë. Pranon deri në 1 000 000 numra për interval, me kufi të sipërm deri në 10¹². Numërimi mbulon gjithë intervalin dhe listohen 2000 numrat e parë të thjeshtë. Për shembull, mes 1 dhe 100 ka 25 numra të thjeshtë dhe nën një milion ka 78 498.

Funksionon në shfletuesin tënd. Asgjë nga ajo që shkruan nuk dërgohet te një server.