Created
September 13, 2020 23:13
-
-
Save foxqstm/11700775c6eaceebe2d0d52c7025711a to your computer and use it in GitHub Desktop.
cyclotomic polynomial method ver 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 12, | |
"metadata": { | |
"scrolled": false | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"the number of primes:100\n", | |
"0 % 1\n", | |
"1.0 % 2\n", | |
"2.0 % 3\n", | |
"3.0 % 4\n", | |
"4.0 % 5\n", | |
"5.0 % 6\n", | |
"6.0 % 7\n", | |
"7.0 % 8\n", | |
"8.0 % 9\n", | |
"9.0 % 10\n", | |
"10.0 % 11\n", | |
"11.0 % 12\n", | |
"12.0 % 13\n", | |
"13.0 % 14\n", | |
"14.0 % 15\n", | |
"15.0 % 16\n", | |
"16.0 % 17\n", | |
"17.0 % 18\n", | |
"18.0 % 19\n", | |
"19.0 % 20\n", | |
"20.0 % 21\n", | |
"21.0 % 22\n", | |
"22.0 % 23\n", | |
"23.0 % 24\n", | |
"24.0 % 25\n", | |
"25.0 % 26\n", | |
"26.0 % 27\n", | |
"27.0 % 28\n", | |
"28.0 % 29\n", | |
"29.0 % 30\n", | |
"30.0 % 31\n", | |
"31.0 % 32\n", | |
"32.0 % 33\n", | |
"33.0 % 34\n", | |
"34.0 % 35\n", | |
"35.0 % 36\n", | |
"36.0 % 37\n", | |
"37.0 % 38\n", | |
"38.0 % 39\n", | |
"39.0 % 40\n", | |
"40.0 % 41\n", | |
"41.0 % 42\n", | |
"42.0 % 43\n", | |
"43.0 % 44\n", | |
"44.0 % 45\n", | |
"45.0 % 46\n", | |
"46.0 % 47\n", | |
"47.0 % 48\n", | |
"48.0 % 49\n", | |
"49.0 % 50\n", | |
"50.0 % 51\n", | |
"51.0 % 52\n", | |
"52.0 % 53\n", | |
"53.0 % 54\n", | |
"54.0 % 55\n", | |
"55.0 % 56\n", | |
"56.0 % 57\n", | |
"57.0 % 58\n", | |
"58.0 % 59\n", | |
"59.0 % 60\n", | |
"60.0 % 61\n", | |
"61.0 % 62\n", | |
"62.0 % 63\n", | |
"63.0 % 64\n", | |
"64.0 % 65\n", | |
"65.0 % 66\n", | |
"66.0 % 67\n", | |
"67.0 % 68\n", | |
"68.0 % 69\n", | |
"69.0 % 70\n", | |
"70.0 % 71\n", | |
"71.0 % 72\n", | |
"72.0 % 73\n", | |
"73.0 % 74\n", | |
"74.0 % 75\n", | |
"75.0 % 76\n", | |
"76.0 % 77\n", | |
"77.0 % 78\n", | |
"78.0 % 79\n", | |
"79.0 % 80\n", | |
"80.0 % 81\n", | |
"81.0 % 82\n", | |
"82.0 % 83\n", | |
"83.0 % 84\n", | |
"84.0 % 85\n", | |
"85.0 % 86\n", | |
"86.0 % 87\n", | |
"87.0 % 88\n", | |
"88.0 % 89\n", | |
"89.0 % 90\n", | |
"90.0 % 91\n", | |
"91.0 % 92\n", | |
"92.0 % 93\n", | |
"93.0 % 94\n", | |
"94.0 % 95\n", | |
"95.0 % 96\n", | |
"96.0 % 97\n", | |
"97.0 % 98\n", | |
"98.0 % 99\n", | |
"99.0 % 100\n", | |
"N= 1\n", | |
"π(N)= 100\n", | |
"full time 0.015504837036132812 [s]\n", | |
"12709189\n", | |
"0 %\n", | |
"full time 0.0 [s]\n", | |
"Ans: 12709189 = 3571 * 3559\n", | |
"391961320150251294647\n", | |
"0 %\n", | |
"full time 0.0 [s]\n", | |
"Ans: 391961320150251294647 = 2147483647 * 182521213001\n", | |
"233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"1790707753365795418841729699379193276395981524363782327873718589639655966058578374254964039644910359346857311359948708984278578450069871685344678652553655035251602806563637363071753327728754995053415389279785107516999221971781597724733184279534477239566789173532366357270583106789\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"30502351862940031577691995198949664002982179597487683486715266186733160876943419156362946151249328917515864630224371171221716993844781534383325603218163254920110064990807393285889718524383600251199650576597076902947432221039432760575157628357292075495937664206199565578681309135044121854119\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"276931556780344213902868906164723309223760836398395325400503672280937582471494739461900602187562551243171865731050750745462388288171212746300721613469564396741836389979086904304472476001839015983033451909174663464663867829125664459895575157178816900228792711267471958357574416714366499722090015674047\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"133294399882575758380143779458803658621711224322668460285458826191727627667054255404674269333491950155273493343140718228407463573528003686665212740575911870128339157499072351179666739658503429931021985160714113146720277365006623692721807916355914275519065334791400296725853788916042959771420436564784273910949\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"1848210397825850670380148517702559371400899745254512521925707445580334710601412527675708297932857843901388104766898429433126419139462696524583464983724651631481888473364151368736236317783587518465017087145416734026424615690611620116380982484120857688483676576094865930188367141388795454378671343386258291687641\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"21368106964100717960120874145003772958637679383727933523150686203631965523578837094085435000951700943373838321997220564166302488321590128061531285010636857163897899811712284013921068534616772684717323224436400485097837112174432182703436548357540610175031371364893034379963672249152120447044722997996160892591129924218437\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"121870863310605869313817398014332524915771068622605522040866660001748138323813524568024259035558807228052611110790898823037176326388561409009333778630890634828167900405006112727432172179976427017137792606951424995281839383708354636468483926114931976844939654102090966520978986231260960498370992377930421701862444655244698696759267\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"2690987062294695111996484658008361875931308730357496490239672429933215694995275858877122326330883664971511275673199794677960841323240693443353204889858591766765807522315638843948076220761775866259739752361275228111366001104150630004691128152106812042872285697735145105026966830649540003659922618399694276990464815739966698956947129133275233\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"26507199951735394734498120973736811015297864642115831624674545482293445855043495841191504413349124560193160478146528433707807716865391982823061751419151606849655575049676468644737917071142487312863146816801954812702917123189212728868259282632393834443989482096498000219878377420094983472636679089765013603382322972552204068806061829535529820731640151\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"218682020234317263146640637228579265464915856482838406521712186637422774544877649638896808173342116436377521579949695169845394824866781413047516721975240052350576247238785129338002757406892629970748212734663781952170745916609168935837235996278783280225742175701130252626518426356562342682345652253987471761591019113926725623095606566457918240614767013806590649\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"1888287707234383972842703127997127272470910519387718062380985523004987076701721281993726195254903980001896112258671262466144228850274568145436317048469073794495250347974943216943521462713202965796237266310948224934556725414915442700993152879235272779266578292207161032746297546080025793864030543617862620878802244305286292772467355603044265985905970622730682658082529621\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"30135004431202116003565860241012769924921679977958392035283632366105785657918270750937407901898070219843622821090980641477056850056514799336625349678549218794180711634478735831265177285887805862071748980072533360656419736316535822377792634235019526468475796787118257207337327341698664061454252865816657556977260763553328252421574633011335112031733393397168350585519524478541747311\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"268040194118238845450103707934665606536694174908285267872982242439770917825046230024728489676042825623316763136454136724676849961188128997344512282129891630084759485063423604911639099585186833094019957687550377834977803400653628695534490436743728187025341405841406315236881249848600505622302828534189804007954474358650330462487514752974123986970880843210371763922883127855444022091083492089\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"2014096878945207511726700485783442547915321782072704356103039129009966793396141985086509455102260403208695558793091390340438867513766123418942845301603261911930567685648626153212566300102683464717478365971313989431406854640516317519403149294308737302321684840956395183222117468443578509847947119995373645360710979599471328761075043464682551112058642299370598078702810603300890715874500584758146849481\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"19653601479938761414239452741787457079262692944398807468279711209925174217701079138139324539033381077755540830342989643633394137538983355218902490897764441296847433275460853182355059915490590169155909870689251647778520385568812706350693720915645943335281565012939241331867051414851378568457417661501594376063244163040088180887087028771717321932252992567756075264441680858665410918431223215368025334985424358839\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"209136630247651073165255642316333073700965362660524505479852295994129273025818983735700761887526097496489535254849254663948005091692193449062731454136342427186266197097846022969248579454916155633686388106962365337549155747268356466658384680996435419155013602317010591744105651749369012554532024258150373034059528878269258139126839427564311148202923131937053527161657901326732705143817744164107601735413785886836578207979\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"3534635645620271361541209209607897224734887106182307093292005188843884213420695035531516325888970426873310130582000012467805106432116010499008974138677724241907444538851271730464985654882214412422106879451855659755824580313513382070785777831859308900851761495284515874808406228585310317964648830289141496328996622685469256041007506727884038380871660866837794704723632316890465023570092246473915442026549955865931709542468648109541\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"26014282119556025900707884873713205505398108045952352894235085896633912708374310252674800592426746319007978890065337573160541942868114065643853327229484502994233222617112392660635752325773689366745234119224790516838789368452481803077294973049597108473379738051456732631199164835297036074054327529666307812234597766390750441445314408171802070904072739275930410299359006059619305590701939627725296116299946059898442103959412221518213407370491\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n" | |
] | |
}, | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"198463423714283662349723072186113142778946286925886208987853800987159869256900787915916842423672625297046526736867114939854460034942655873583931553781158032447061155145160770580926824366573211993981662614635734812647448360573856313224749171552699727811551490561895325344395743588150359341484236709604618276434347948498243152515106628556992696242074513657383842554978233909962839183287667419172988072221996532403300258906083211160744508191024837057033\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"1786856020404004433262103789212844585886400086993882955081051578507634807524146407881981216968139444577147633460848868774625431829282860339614956262303635645546753552581286559710032014178315212224644686666427660441466419337888368932452217321354860484353296131403821175862890998598653858373835628654351880480636223164308238684873105235011577671552114945370886842810830301698313339004163655154668570049008475016448080768256389182668489641536264864604484300734909\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"17051473784681185209081599238887028025183255852149159683588918369809675398036897711442383602526314519192366612270595815510311970886116763177669964411814095748660238871306469830461919135901638237924444074122866545522954536883748558744552128950445218096208188788876324395049362376806579941053305386217595984047709603954312447692725276887594590658792939924609261264788572032212334726855302571883565912645432522077138010357669555555071044090857089539320564963576770285413369\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"302657075295090869739730250315591803589112283576939858395529632634305976144571441696598170401251852159138533455982172343712313383247732107268535247763784105186549246199888070331088462855743520880671299302895546822695492968577380706795842802200829411198422297326020823369315258921162990168697393348736236081296604185145690639952829781767901497605213955485328141965346769742597479306858645849268328985687423881853632604706175564461719396117318298679820785491875674946700413680932103\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"1860239127076846517198369354026076875269515930592839150201028353837031025971373852216474332794920643399906822553185507255460678213880084116286603739332465781718042017172224499540303152935478714013629615010650024865526886634157459758925793594165651020789220067311416926076949777767604906107061937873540601594274731617619377537419071307115490065850326946551649682856865437718319058695376406980449326388934924579147508558589808491904883853150769224537555274811376719096144119390052199027715691\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"18971941337486266563305347433172025272371835919534283031845811230624504588707687605943212347625766427494554764419515427586743205659317254669946604982419730160103812521528540068803151640161162396312837062979326593940508107758169447860417214110246410380402787011098086642148000255604546876251377453934182215494821277335671735153472656328448001134940926442438440198910908603252678814785060113207728717281994244511323201949222955423789860663107489107472242561739680319169243814676235712934292299974411361\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"22701801293785014193580405120204586741061235962766583907094021879215171483119139894870133091111044901683400949483846818299518041763507948922590774925466088171879259465921026597046700449819899096862039460017743094473811056991294128542891880855362707407670722593737772666973440977361243336397308051763091506836310795312607239520365290032105848839507981452307299417185715796297454995023505316040919859193718023307414880446217922800831766040938656344571034778553457121080530736394535923932651866030515041060966437313323672831539323500067937107541955437362433248361242525945868802353916766181532375855504886901432221349733\n", | |
"0 %\n", | |
"10.0 %\n", | |
"20.0 %\n", | |
"30.0 %\n", | |
"40.0 %\n", | |
"50.0 %\n", | |
"60.0 %\n", | |
"70.0 %\n", | |
"80.0 %\n", | |
"90.0 %\n", | |
"FIN\n" | |
] | |
} | |
], | |
"source": [ | |
"import math\n", | |
"import sympy\n", | |
"import time\n", | |
"\n", | |
"plist2310 = [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, 103,\n", | |
"107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,\n", | |
"227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,\n", | |
"349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,\n", | |
"467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,\n", | |
"613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,\n", | |
"751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,\n", | |
"887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,\n", | |
"1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,\n", | |
"1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,\n", | |
"1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,\n", | |
"1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,\n", | |
"1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627,\n", | |
"1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777,\n", | |
"1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907,\n", | |
"1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,\n", | |
"2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,\n", | |
"2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309\n", | |
"]\n", | |
"\n", | |
"cplist2310 = [1, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,109,\n", | |
"113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223,\n", | |
"227, 229, 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 299, 307, 311, 313, 317,\n", | |
"323, 331, 337, 347, 349, 353, 359, 361, 367, 373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421,\n", | |
"431, 433, 437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499, 503, 509, 521, 523, 527,\n", | |
"529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619,\n", | |
"629, 631, 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701, 703, 709, 713, 719, 727,\n", | |
"731, 733, 739, 743, 751, 757, 761, 767, 769, 773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827,\n", | |
"829, 839, 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901, 907, 911, 919, 923, 929,\n", | |
"937, 941, 943, 947, 949, 953, 961, 967, 971, 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021,\n", | |
"1027, 1031, 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079, 1081, 1087, 1091, 1093, 1097,\n", | |
"1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151, 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189,\n", | |
"1193, 1201, 1207, 1213, 1217, 1219, 1223, 1229, 1231, 1237, 1241, 1247, 1249, 1259, 1261, 1271, 1273,\n", | |
"1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319, 1321, 1327, 1333, 1339, 1343, 1349,\n", | |
"1357, 1361, 1363, 1367, 1369, 1373, 1381, 1387, 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429,\n", | |
"1433, 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1501, 1511,\n", | |
"1513, 1517, 1523, 1531, 1537, 1541, 1543, 1549, 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597,\n", | |
"1601, 1607, 1609, 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667, 1669, 1679,\n", | |
"1681, 1691, 1693, 1697, 1699, 1703, 1709, 1711, 1717, 1721, 1723, 1733, 1739, 1741, 1747, 1751, 1753,\n", | |
"1759, 1763, 1769, 1777, 1781, 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843,\n", | |
"1847, 1849, 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901, 1907, 1909, 1913, 1919, 1921,\n", | |
"1927, 1931, 1933, 1937, 1943, 1949, 1951, 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003,\n", | |
"2011, 2017, 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071, 2077, 2081, 2083,\n", | |
"2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131, 2137, 2141, 2143, 2147, 2153, 2159, 2161, 2171,\n", | |
"2173, 2179, 2183, 2197, 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249, 2251,\n", | |
"2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297, 2309\n", | |
"]\n", | |
"\n", | |
"def intsqrt(n):\n", | |
" dig=0\n", | |
" while pow(10,2*dig) < n:\n", | |
" dig+=1\n", | |
" \n", | |
" sq=0\n", | |
" for k in reversed(range(0,dig+1)):\n", | |
" for l in range(0,10):\n", | |
" sq+=10**k\n", | |
" if sq*sq==n:\n", | |
" break\n", | |
" if sq*sq>n:\n", | |
" sq-=10**k\n", | |
" break\n", | |
" return sq\n", | |
"\n", | |
"def is_prime(N):\n", | |
" if N<2310:\n", | |
" if N in plist2310:\n", | |
" return True\n", | |
" else:\n", | |
" return False\n", | |
" else:\n", | |
" for p in plist2310:\n", | |
" if N%p==0:\n", | |
" return False\n", | |
" \n", | |
" bound=math.floor(N**0.5)\n", | |
" for cp in cplist2310:\n", | |
" maxk=math.floor((bound-cp)/2310)\n", | |
" for k in range(1,maxk+1):\n", | |
" q=2310*k+cp\n", | |
" if q>bound:\n", | |
" break\n", | |
" if N%q==0:\n", | |
" return False\n", | |
"\n", | |
" return True\n", | |
"\n", | |
"\n", | |
"def primorial(N,pplist):\n", | |
"\n", | |
" prim=1\n", | |
" for k in range(0,N):\n", | |
" prim*=pplist[k]\n", | |
" \n", | |
" return prim\n", | |
" \n", | |
"rsa100=1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139\n", | |
"rsa110=35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667\n", | |
"rsa120=227010481295437363334259960947493668895875336466084780038173258247009162675779735389791151574049166747880487470296548479\n", | |
"rsa129=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541\n", | |
"rsa130=1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557\n", | |
"rsa140=21290246318258757547497882016271517497806703963277216278233383215381949984056495911366573853021918316783107387995317230889569230873441936471\n", | |
"rsa150=155089812478348440509606754370011861770654545830995430655466945774312632703463465954363335027577729025391453996787414027003501631772186840890795964683\n", | |
"rsa155=10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897\n", | |
"rsa160=2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753\n", | |
"rsa170=26062623684139844921529879266674432197085925380486406416164785191859999628542069361450283931914514618683512198164805919882053057222974116478065095809832377336510711545759\n", | |
"rsa180=191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041\n", | |
"rsa190=1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481\n", | |
"rsa200=27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983\n", | |
"rsa210=245246644900278211976517663573088018467026787678332759743414451715061600830038587216952208399332071549103626827191679864079776723243005600592035631246561218465817904100131859299619933817012149335034875870551067\n", | |
"rsa220=2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261\n", | |
"rsa230=17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689\n", | |
"rsa232=1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079\n", | |
"rsa240=124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099\n", | |
"rsa250=2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937\n", | |
"rsa260=22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199\n", | |
"rsa270=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207\n", | |
"rsa280=1790707753365795418841729699379193276395981524363782327873718589639655966058578374254964039644910359346857311359948708984278578450069871685344678652553655035251602806563637363071753327728754995053415389279785107516999221971781597724733184279534477239566789173532366357270583106789\n", | |
"rsa290=30502351862940031577691995198949664002982179597487683486715266186733160876943419156362946151249328917515864630224371171221716993844781534383325603218163254920110064990807393285889718524383600251199650576597076902947432221039432760575157628357292075495937664206199565578681309135044121854119\n", | |
"rsa300=276931556780344213902868906164723309223760836398395325400503672280937582471494739461900602187562551243171865731050750745462388288171212746300721613469564396741836389979086904304472476001839015983033451909174663464663867829125664459895575157178816900228792711267471958357574416714366499722090015674047\n", | |
"rsa309=133294399882575758380143779458803658621711224322668460285458826191727627667054255404674269333491950155273493343140718228407463573528003686665212740575911870128339157499072351179666739658503429931021985160714113146720277365006623692721807916355914275519065334791400296725853788916042959771420436564784273910949\n", | |
"rsa310=1848210397825850670380148517702559371400899745254512521925707445580334710601412527675708297932857843901388104766898429433126419139462696524583464983724651631481888473364151368736236317783587518465017087145416734026424615690611620116380982484120857688483676576094865930188367141388795454378671343386258291687641\n", | |
"rsa320=21368106964100717960120874145003772958637679383727933523150686203631965523578837094085435000951700943373838321997220564166302488321590128061531285010636857163897899811712284013921068534616772684717323224436400485097837112174432182703436548357540610175031371364893034379963672249152120447044722997996160892591129924218437\n", | |
"rsa330=121870863310605869313817398014332524915771068622605522040866660001748138323813524568024259035558807228052611110790898823037176326388561409009333778630890634828167900405006112727432172179976427017137792606951424995281839383708354636468483926114931976844939654102090966520978986231260960498370992377930421701862444655244698696759267\n", | |
"rsa340=2690987062294695111996484658008361875931308730357496490239672429933215694995275858877122326330883664971511275673199794677960841323240693443353204889858591766765807522315638843948076220761775866259739752361275228111366001104150630004691128152106812042872285697735145105026966830649540003659922618399694276990464815739966698956947129133275233\n", | |
"rsa350=26507199951735394734498120973736811015297864642115831624674545482293445855043495841191504413349124560193160478146528433707807716865391982823061751419151606849655575049676468644737917071142487312863146816801954812702917123189212728868259282632393834443989482096498000219878377420094983472636679089765013603382322972552204068806061829535529820731640151\n", | |
"rsa360=218682020234317263146640637228579265464915856482838406521712186637422774544877649638896808173342116436377521579949695169845394824866781413047516721975240052350576247238785129338002757406892629970748212734663781952170745916609168935837235996278783280225742175701130252626518426356562342682345652253987471761591019113926725623095606566457918240614767013806590649\n", | |
"rsa370=1888287707234383972842703127997127272470910519387718062380985523004987076701721281993726195254903980001896112258671262466144228850274568145436317048469073794495250347974943216943521462713202965796237266310948224934556725414915442700993152879235272779266578292207161032746297546080025793864030543617862620878802244305286292772467355603044265985905970622730682658082529621\n", | |
"rsa380=30135004431202116003565860241012769924921679977958392035283632366105785657918270750937407901898070219843622821090980641477056850056514799336625349678549218794180711634478735831265177285887805862071748980072533360656419736316535822377792634235019526468475796787118257207337327341698664061454252865816657556977260763553328252421574633011335112031733393397168350585519524478541747311\n", | |
"rsa390=268040194118238845450103707934665606536694174908285267872982242439770917825046230024728489676042825623316763136454136724676849961188128997344512282129891630084759485063423604911639099585186833094019957687550377834977803400653628695534490436743728187025341405841406315236881249848600505622302828534189804007954474358650330462487514752974123986970880843210371763922883127855444022091083492089\n", | |
"rsa400=2014096878945207511726700485783442547915321782072704356103039129009966793396141985086509455102260403208695558793091390340438867513766123418942845301603261911930567685648626153212566300102683464717478365971313989431406854640516317519403149294308737302321684840956395183222117468443578509847947119995373645360710979599471328761075043464682551112058642299370598078702810603300890715874500584758146849481\n", | |
"rsa410=19653601479938761414239452741787457079262692944398807468279711209925174217701079138139324539033381077755540830342989643633394137538983355218902490897764441296847433275460853182355059915490590169155909870689251647778520385568812706350693720915645943335281565012939241331867051414851378568457417661501594376063244163040088180887087028771717321932252992567756075264441680858665410918431223215368025334985424358839\n", | |
"rsa420=209136630247651073165255642316333073700965362660524505479852295994129273025818983735700761887526097496489535254849254663948005091692193449062731454136342427186266197097846022969248579454916155633686388106962365337549155747268356466658384680996435419155013602317010591744105651749369012554532024258150373034059528878269258139126839427564311148202923131937053527161657901326732705143817744164107601735413785886836578207979\n", | |
"rsa430=3534635645620271361541209209607897224734887106182307093292005188843884213420695035531516325888970426873310130582000012467805106432116010499008974138677724241907444538851271730464985654882214412422106879451855659755824580313513382070785777831859308900851761495284515874808406228585310317964648830289141496328996622685469256041007506727884038380871660866837794704723632316890465023570092246473915442026549955865931709542468648109541\n", | |
"rsa440=26014282119556025900707884873713205505398108045952352894235085896633912708374310252674800592426746319007978890065337573160541942868114065643853327229484502994233222617112392660635752325773689366745234119224790516838789368452481803077294973049597108473379738051456732631199164835297036074054327529666307812234597766390750441445314408171802070904072739275930410299359006059619305590701939627725296116299946059898442103959412221518213407370491\n", | |
"rsa450=198463423714283662349723072186113142778946286925886208987853800987159869256900787915916842423672625297046526736867114939854460034942655873583931553781158032447061155145160770580926824366573211993981662614635734812647448360573856313224749171552699727811551490561895325344395743588150359341484236709604618276434347948498243152515106628556992696242074513657383842554978233909962839183287667419172988072221996532403300258906083211160744508191024837057033\n", | |
"rsa460=1786856020404004433262103789212844585886400086993882955081051578507634807524146407881981216968139444577147633460848868774625431829282860339614956262303635645546753552581286559710032014178315212224644686666427660441466419337888368932452217321354860484353296131403821175862890998598653858373835628654351880480636223164308238684873105235011577671552114945370886842810830301698313339004163655154668570049008475016448080768256389182668489641536264864604484300734909\n", | |
"rsa470=17051473784681185209081599238887028025183255852149159683588918369809675398036897711442383602526314519192366612270595815510311970886116763177669964411814095748660238871306469830461919135901638237924444074122866545522954536883748558744552128950445218096208188788876324395049362376806579941053305386217595984047709603954312447692725276887594590658792939924609261264788572032212334726855302571883565912645432522077138010357669555555071044090857089539320564963576770285413369\n", | |
"rsa480=302657075295090869739730250315591803589112283576939858395529632634305976144571441696598170401251852159138533455982172343712313383247732107268535247763784105186549246199888070331088462855743520880671299302895546822695492968577380706795842802200829411198422297326020823369315258921162990168697393348736236081296604185145690639952829781767901497605213955485328141965346769742597479306858645849268328985687423881853632604706175564461719396117318298679820785491875674946700413680932103\n", | |
"rsa490=1860239127076846517198369354026076875269515930592839150201028353837031025971373852216474332794920643399906822553185507255460678213880084116286603739332465781718042017172224499540303152935478714013629615010650024865526886634157459758925793594165651020789220067311416926076949777767604906107061937873540601594274731617619377537419071307115490065850326946551649682856865437718319058695376406980449326388934924579147508558589808491904883853150769224537555274811376719096144119390052199027715691\n", | |
"rsa500=18971941337486266563305347433172025272371835919534283031845811230624504588707687605943212347625766427494554764419515427586743205659317254669946604982419730160103812521528540068803151640161162396312837062979326593940508107758169447860417214110246410380402787011098086642148000255604546876251377453934182215494821277335671735153472656328448001134940926442438440198910908603252678814785060113207728717281994244511323201949222955423789860663107489107472242561739680319169243814676235712934292299974411361\n", | |
"rsa617=22701801293785014193580405120204586741061235962766583907094021879215171483119139894870133091111044901683400949483846818299518041763507948922590774925466088171879259465921026597046700449819899096862039460017743094473811056991294128542891880855362707407670722593737772666973440977361243336397308051763091506836310795312607239520365290032105848839507981452307299417185715796297454995023505316040919859193718023307414880446217922800831766040938656344571034778553457121080530736394535923932651866030515041060966437313323672831539323500067937107541955437362433248361242525945868802353916766181532375855504886901432221349733\n", | |
"\n", | |
"ntest=12709189\n", | |
"ntest2=391961320150251294647\n", | |
"nlist=[ntest,ntest2,rsa100,rsa110,rsa120,rsa129,rsa130,rsa140,rsa150,rsa155,rsa160,rsa170,rsa180,rsa190,rsa200,rsa210,rsa220,rsa230,rsa232,rsa240,rsa250,rsa260,rsa270,rsa280,rsa290,rsa300,rsa309,rsa310,rsa320,rsa330,rsa340,rsa350,rsa360,rsa370,rsa380,rsa390,rsa400,rsa410,rsa420,rsa430,rsa440,rsa450,rsa460,rsa470,rsa480,rsa490,rsa500,rsa617]\n", | |
"nlist=[ntest,ntest2,rsa270,rsa280,rsa290,rsa300,rsa309,rsa310,rsa320,rsa330,rsa340,rsa350,rsa360,rsa370,rsa380,rsa390,rsa400,rsa410,rsa420,rsa430,rsa440,rsa450,rsa460,rsa470,rsa480,rsa490,rsa500,rsa617]\n", | |
"p100=37975227936943673922808872755445627854565536638199\n", | |
"\n", | |
"textnp=input('the number of primes:')\n", | |
"np=int(textnp)\n", | |
"sf=time.time()\n", | |
"\n", | |
"Nmax=10**20\n", | |
"countp=0\n", | |
"countmax=np\n", | |
"#countmax=5*10**6\n", | |
"pplist=[]\n", | |
"\n", | |
"delta=0.01\n", | |
"percent=0\n", | |
"\n", | |
"for N in range(2,min(2310,Nmax)+1):\n", | |
" if is_prime(N):\n", | |
" pplist.append(N)\n", | |
" countp+=1\n", | |
" if countp/countmax>percent:\n", | |
" print(round(percent*100,2),'%',countp)\n", | |
" percent+=delta\n", | |
" if countp==countmax:\n", | |
" break\n", | |
" \n", | |
"if Nmax> 2310:\n", | |
" N=1\n", | |
" makl=math.floor(Nmax/2310)\n", | |
" for l in range(1,makl+1):\n", | |
" if countp==countmax:\n", | |
" break\n", | |
" if N>Nmax:\n", | |
" break\n", | |
" if countp/countmax>percent:\n", | |
" print(round(percent*100,2),'%',countp)\n", | |
" percent+=delta\n", | |
" for cp in cplist2310:\n", | |
" N=2310*l+cp\n", | |
" if N>Nmax:\n", | |
" break\n", | |
" if is_prime(N):\n", | |
" pplist.append(N)\n", | |
" countp+=1\n", | |
" if countp==countmax:\n", | |
" break\n", | |
"\n", | |
"print('N=',N)\n", | |
"print('π(N)=',countp)\n", | |
"ff=time.time()\n", | |
"print('full time',ff-sf,'[s]')\n", | |
"\n", | |
"\n", | |
"maxx=10**1\n", | |
"prim=primorial(np,pplist)\n", | |
"k=prim\n", | |
"delta=0.1\n", | |
"\n", | |
"for n in nlist:\n", | |
" sf=time.time()\n", | |
" print(n)\n", | |
" percent=0\n", | |
" g=1\n", | |
" xx=1\n", | |
" BOOL=False\n", | |
" BOOLpq=True\n", | |
" BOOLfirst=True\n", | |
" for x0 in range(1,maxx+1):\n", | |
" if BOOL:\n", | |
" break\n", | |
" x=prim\n", | |
" if x0/maxx>percent:\n", | |
" print(round(percent*100,2),'%')\n", | |
" percent+=delta\n", | |
"# a_n=pow(x,k,n)-1\n", | |
" if BOOLfirst:\n", | |
" a_n=pow(x,k,n)-1\n", | |
" else:\n", | |
" a_n=pow(xx,k,n)-1\n", | |
" xx=(a_n*xx)%n\n", | |
" g=math.gcd(xx,n)\n", | |
" if g==n and BOOLpq:\n", | |
" BOOLpq=False\n", | |
" print('pq')\n", | |
" if g!=1 and g!=n:\n", | |
" ff=time.time()\n", | |
" print('full time',ff-sf,'[s]')\n", | |
" p=g\n", | |
" q=n//p\n", | |
" if p*q==n:\n", | |
" print('Ans:',n,'=',p,'*',q)\n", | |
" BOOL=True\n", | |
" break\n", | |
"\n", | |
"\n", | |
"print('FIN')" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.6.5" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment