Реализации алгоритмов/Тест Пепина

Материал из Викиучебника — открытых книг для открытого мира

Примеры программных реализаций теста Пепина.

Python[править]

Пример реализации теста на языке Python:

base = 3

while True:
    try:
        character = int(input('Input an index of the Fermat number, please: '))
        break
    except ValueError:
        print("The index should be a number. Try again, please.")

power = 2 ** character - 1
fermat_number = 2 ** (2 ** character) + 1

for i in range(1, power+1):
    base = (base ** 2) % fermat_number

if base == (fermat_number - 1):
    print ('The number F' + str(character) + ' is prime')
else:
    print ('The number F' + str(character) + ' is composite')

print('F' + str(character) + ' = ' + str(fermat_number))

Пример работы программы:

Input an index of the Fermat number, please: 15
The number F15 is composite
F15 = 1415461031044954789001553027744951601348130711472388167234385748272366634240845253596025356476648415075475872961656126492389808579544737848881938296250873191743927793544913011050162651277957029846960211783242933521207545413484969856851851141288515163201482995389055097460622098635675003353929224278582935664416262572773308153277514346480313371988612629481483562438178928958867777850072198316174841251955590996672018645093640850803679630220367201383844866791449284737518262813123083439037243678440420897139923778278952770312318778329004894547065489077596835396017153603170050371302014762443872701111379554484309718662306883776010475348441493600491943479041271992920195331983064930106164727241438940877685164658948654886171641124473975626241632750150126655369981021293570066042305482486040883165635862835728637046058352403756085745691239473897891999085976345203704659967157427239535836507133656908815246080139195569461072006301590372954830738644391138016065344131131207604264053897440828904662047183234377547427287691941741535946510882990904477863185473798528388060457568927943633923928872681927502029572963130840854853739937076881035646179383055483433876051402037614424748902969018159186519811051545367967103767182819709135479019131683309330797374408197339831527239040715908112213095126770717606001288898889370710896248862361503869205214536908258196921765593065325392836332142594411134603475509366028145690306350601859295261296263331018682276317567749534571058772235567679556920240789109070521253987131031263902293034744367356932509952188828475362311316445284228640489421809263738423630931243024914587863928134719186104164660605356001591962778646378295413659770782646979236289062616442418071571039282551289348848274522893059561717860194034698241804887531275078109603637160495907579995366419636417028927573391670580796818526074226095014375189438579216071677540766085605604106123036669667434677723472675564458991671268414100801031453917736665947284956674884035306621286465183798693852599803324619865181856244422079233687294508536408521087418873908498202710597080474480249818858011490930518512713798803629101638716278578874145214429026186276602289012484526830076647356828764878327726719816428678904207944456894393185983090347045176886732326253912297649524439880403701430566761380359925558522718201954287517587367247510777678934664472548647787048306330770862370015525858005479756471499227244901142805749769564184753211967223226212964165678856604892416984915097422960534122333453876981279243565766391796311605149222628328255333061543877525846029404507128890053189442527544665141513571136187126874914601669750392486100507568442046831780631032540574077944274454228087639241736818505163759910365131990632947462993204585218122431992323864244947394390438656356424037471932484452186545692102503479070599953823165194211019696760575264426802848303031804305733532228050180286034175168918827460626042268658295140706915047189049492578996650494005882337071150004868956193406593184838633694068409823903437144417376039174235011053228846851424217955172902918651003610984108402650929359396305634313047088725113039076811940090109855578285937829164213576612822210347957745947331047482525346602542653176899809278808232796557531832150249769253600667902268029661700149632868541956266119528042486534014778779846981761033155007262730162675954520221887384710387051721829271917592295057169589539706361671082094809405871790468623234895914796464390019259167513771864832869036015645542195008456098615038348028400803005801944957156282746379539470250603755465358786281476086044567893715130635914946085361612372742732638037372287633897118303250036355897758209569010246051563429109255864938245524550200580218274314809738075022775651220374105227215906205292751918667060475328593225367793061070422108733800983855507591806413460964585595316359971179284283604731468668545484761381747591639736453419896449323486397030776397761202590467637505473390222249456724093238682557762781839530938233751281999608711356147835655195236666056355678841889862284014674059052995170220711404445012766642203314592371712594877968343265210232798135023299117318191770365123807086704381809759602260151612996896994294186084475619138121455294389585874237791634701296124550179672059485838256445846530599137662480841344376503989244633345016070887198120421435575726237189312161818021548006389501182393441712142044953072264016676799011624620312246468554654371544717355227740157629086739710675845209992133342035144038961065892653392182875622932670067798433934891709519877850794219491447988160171932331006495620280094149464379450153085406225081471879585894087916092141623752345112751067703166403681162331920291740847388957632311053342426152947324011627922225878539935022974616062774839110489080094174972841068102006645677499293769091362853719300958775222088670909723895414866464400756314470281962034276531512544009726174649399937581739718117982417360985958259468485436586733686659771030677664677905401522360041892481951454135360540917411098412286723830672712910603386748136348878056545746112142111116659985782398275627122449414307140749404884060753863706024281031485538666133332835597817514616331728118982180628823657668668099621799842011158020767772792912298768785614574416019320546196793486018677884550715870608004988829978148966980770136884353226949853654541655837029498017031085943660440466076019479435181045436897845351048788440102268677798257134774081674357195358847761226603653040273985441982221318087815835107317571211841215825606453348521097936413520295998260751040778703740366309871999114717441069182825782996299411623087415008910941303284182131584799816210728034255555687956785287887098941927737599159824398527573423117728252839768919145018117995597946282264946523741691180858441194373387098969530126834014923656627849129062189145572870212225909464530919531634090206371146321663797279805760028495288084848179380053931435604182517516600823936737919915974103591167638898871754018470172589234989397051893028574365288890303780239194622538215532212735555299397542845350629361560347195459286729561168235383428930828378887678197590624110372267338756668414899526138480866747114831414687579691636020586013635675559033488649721062244142787960404056961306176022981242840984825421797150393909713884990708008654327558025619074213270714252431515171638994505720144347502185848528129000055629703422695425047209518177577128511315492059613722366724615343968357332924191178041956753132941596322101250417068813977303498033940613791099720174786773844696734034010269139553878212387108508158622839733593634918975616613368243882808391509244806809337882965338701545504691589517650472239580754189547649790038026506707709763098148746524031013800531890876858227360501676161874661946431647929572555992967298553471152693471452480119897608173336753260124452510815333416409357029633265172614203663326409976153102467083379129588112837280711111346490898947808402062401228963194162711657422998429263579276515414000979053740662733816632981508535128518440258006782392288860903823207436820793041881907093791874917635829854808150640894907127600430185202301457398493533111918994100853753771956293430162566011361163168953462188010231819000213669780447856871248564377584509085888797883747538309181810700615032225563091016689474780253412571338625581817921061549352557588323659562675650563535186144754433556539747098322643609542486120512917463706713059064230762924353617972053492527119192658171851345957700772571841998176036269399889012480745075924980479390349332734102774400008120073461540540571051506971003904623484344762005126345905465893817895377928139596549936720100490013375956605889200767596688065961076003472005585890222594655010430123127351665316862663484785966446263740624564875351640780923703006868107440790271682936043304873579648989978571754898840789184480129570446991029504758616393106487523321312507454036808667210073602144290050619610614738139543285649346986393213102456863793665512533655931941790537619020604730601443181250662019687491711547360597117856977240817110039737153355212454745907787131179578656470567535050192702347739653312290522505871612897990429961857550031033665725647987982751868407294730437319505335782425290324427994308374960806684435416445907817107168298342945182985594111281499472495749501642418042734681158560450241309279063816746067016274795461832774699007774423895748677615395848493765672271957278664546343161609126810028254214659633625223934508931691728584028342356669332635458079957147833789501696835781748234884919093574276330354577841975249603899105407104895787598263630679206627796433754045597409176502438867600537016879169914474754840024311922169647388379952802523847080102439285112565751677726373201688403254466789070713575214256192452449029110040537994627424532403620179880056518721219108771374073638118719073211367295514376708596537294204544099903590754371656178656960170217675832153268164591674004500239073743502648099105624548587493544825479270589742494495181223722329693345468639306990523118995640567042531369577131113159027381808071346991604513906450398219426300899204662435492578485666553974492723173859777485412927016068341515517437115137050372750279278548332799193799400154166442801427310076537020119936073495221974791939759846168942055397357348278178050441024490005893818256958665388971201322931680573846084525016332224646866617490832496084991690171583029352609836490908113464668343829985351590552945284372573978295485097950893072423518605982085487154470155025269025854044646496572448495225343096261896378931482883286657508859228868487844184479087538453974144187004884366561256723404772190847586008543961349071131191708943295337664384184532774661503245910257451923515607711559705478132556040197663414911885143697985464807309297002910250505302287769412337441199360424519160716552890882816796378296881641827981453035207233752063518782778493743827708109913493162932182427627261046280168269958077541122668104633712377857