cyclotomic polynomial method ver 3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the number of primes:100000\n",
      "power:9\n",
      "maxx:1\n",
      "0 % 1\n",
      "1.0 % 1145\n",
      "2.0 % 2116\n",
      "3.0 % 3022\n",
      "4.0 % 4135\n",
      "5.0 % 5204\n",
      "6.0 % 6062\n",
      "7.0 % 7091\n",
      "8.0 % 8119\n",
      "9.0 % 9132\n",
      "10.0 % 10125\n",
      "11.0 % 11116\n",
      "12.0 % 12106\n",
      "13.0 % 13092\n",
      "14.0 % 14064\n",
      "15.0 % 15016\n",
      "16.0 % 16146\n",
      "17.0 % 17115\n",
      "18.0 % 18057\n",
      "19.0 % 19012\n",
      "20.0 % 20132\n",
      "21.0 % 21049\n",
      "22.0 % 22002\n",
      "23.0 % 23095\n",
      "24.0 % 24030\n",
      "25.0 % 25118\n",
      "26.0 % 26019\n",
      "27.0 % 27131\n",
      "28.0 % 28065\n",
      "29.0 % 29150\n",
      "30.0 % 30063\n",
      "31.0 % 31139\n",
      "32.0 % 32026\n",
      "33.0 % 33099\n",
      "34.0 % 34172\n",
      "35.0 % 35064\n",
      "36.0 % 36128\n",
      "37.0 % 37039\n",
      "38.0 % 38088\n",
      "39.0 % 39147\n",
      "40.0 % 40045\n",
      "41.0 % 41094\n",
      "42.0 % 42154\n",
      "43.0 % 43042\n",
      "44.0 % 44096\n",
      "45.0 % 45124\n",
      "46.0 % 46180\n",
      "47.0 % 47051\n",
      "48.0 % 48099\n",
      "49.0 % 49143\n",
      "50.0 % 50021\n",
      "51.0 % 51056\n",
      "52.0 % 52066\n",
      "53.0 % 53098\n",
      "54.0 % 54139\n",
      "55.0 % 55174\n",
      "56.0 % 56031\n",
      "57.0 % 57067\n",
      "58.0 % 58083\n",
      "59.0 % 59123\n",
      "60.0 % 60117\n",
      "61.0 % 61154\n",
      "62.0 % 62018\n",
      "63.0 % 63035\n",
      "64.0 % 64076\n",
      "65.0 % 65080\n",
      "66.0 % 66116\n",
      "67.0 % 67121\n",
      "68.0 % 68127\n",
      "69.0 % 69161\n",
      "70.0 % 70002\n",
      "71.0 % 71012\n",
      "72.0 % 72038\n",
      "73.0 % 73031\n",
      "74.0 % 74036\n",
      "75.0 % 75037\n",
      "76.0 % 76037\n",
      "77.0 % 77038\n",
      "78.0 % 78015\n",
      "79.0 % 79032\n",
      "80.0 % 80051\n",
      "81.0 % 81052\n",
      "82.0 % 82038\n",
      "83.0 % 83005\n",
      "84.0 % 84021\n",
      "85.0 % 85177\n",
      "86.0 % 86016\n",
      "87.0 % 87042\n",
      "88.0 % 88024\n",
      "89.0 % 89006\n",
      "90.0 % 90006\n",
      "91.0 % 91009\n",
      "92.0 % 92024\n",
      "93.0 % 93021\n",
      "94.0 % 94165\n",
      "95.0 % 95136\n",
      "96.0 % 96106\n",
      "97.0 % 97109\n",
      "98.0 % 98104\n",
      "99.0 % 99086\n",
      "N= 1299709\n",
      "π(N)= 100000\n",
      "full time 38.5009765625 [s]\n",
      "1 -th\n",
      "354143482055975082930477037139\n",
      "2 -th\n",
      "296566012218630510011181589087\n",
      "3 -th\n",
      "549439075673072427732096778547\n",
      "full time 4.2755560874938965 [s]\n",
      "Ans: 549439075673072427732096778547 = 9214129979 * 59630054809873919593\n",
      "4 -th\n",
      "103380546665891270055241233827\n",
      "full time 4.212566375732422 [s]\n",
      "Ans: 103380546665891270055241233827 = 8792812211 * 11757392764121579857\n",
      "5 -th\n",
      "689215102160892119973798870383\n",
      "full time 4.500203609466553 [s]\n",
      "Ans: 689215102160892119973798870383 = 9592666507 * 71848124987765940269\n",
      "6 -th\n",
      "525569509824030032829491073779\n",
      "7 -th\n",
      "76490949251817376217531320697\n",
      "8 -th\n",
      "180117443560064734843176941759\n",
      "full time 4.5229127407073975 [s]\n",
      "Ans: 180117443560064734843176941759 = 3732102971 * 48261648984407063629\n",
      "9 -th\n",
      "333385812770747483141338307479\n",
      "full time 4.331939458847046 [s]\n",
      "Ans: 333385812770747483141338307479 = 5761762219 * 57861779104901913541\n",
      "10 -th\n",
      "249976649027694312780027201247\n",
      "full time 4.248290777206421 [s]\n",
      "Ans: 249976649027694312780027201247 = 3283035421 * 76141928725079787307\n",
      "11 -th\n",
      "59410994401967822664824343827\n",
      "pq\n",
      "12 -th\n",
      "145189629490163843606502408091\n",
      "13 -th\n",
      "195746310034675088254938272473\n",
      "full time 4.574495792388916 [s]\n",
      "Ans: 195746310034675088254938272473 = 2326473139 * 84138650368778269507\n",
      "14 -th\n",
      "275892916333077817253695702349\n",
      "full time 4.389383554458618 [s]\n",
      "Ans: 275892916333077817253695702349 = 4209397331 * 65542141698354637279\n",
      "15 -th\n",
      "41524885555975502674044038921\n",
      "16 -th\n",
      "394396012542147094376866729237\n",
      "17 -th\n",
      "450033860982666598946626919851\n",
      "18 -th\n",
      "144639433954365701716040170631\n",
      "full time 4.54124116897583 [s]\n",
      "Ans: 144639433954365701716040170631 = 4560752507 * 31713940568440869733\n",
      "19 -th\n",
      "282042926796243396677157215467\n",
      "full time 4.443357706069946 [s]\n",
      "Ans: 282042926796243396677157215467 = 3931361591 * 71741792319973702637\n",
      "20 -th\n",
      "606937034155743267775921940437\n",
      "full time 4.505606412887573 [s]\n",
      "Ans: 606937034155743267775921940437 = 6991951411 * 86805098960053866967\n",
      "21 -th\n",
      "831403549172751956116848314873\n",
      "22 -th\n",
      "71145852366326944787749773883\n",
      "pq\n",
      "23 -th\n",
      "231200297589624578182572723109\n",
      "24 -th\n",
      "500255792869315297247655581753\n",
      "full time 4.354205369949341 [s]\n",
      "Ans: 500255792869315297247655581753 = 5631160123 * 88837074766541014811\n",
      "25 -th\n",
      "188854219450921105412829439943\n",
      "26 -th\n",
      "108054726127487662851803458861\n",
      "full time 4.282492637634277 [s]\n",
      "Ans: 108054726127487662851803458861 = 1672954763 * 64589149998126795047\n",
      "27 -th\n",
      "267858735845102501093144295601\n",
      "full time 4.7749457359313965 [s]\n",
      "Ans: 267858735845102501093144295601 = 6446216033 * 41552863644944258897\n",
      "28 -th\n",
      "246616623982135038676243268957\n",
      "full time 4.47336220741272 [s]\n",
      "Ans: 246616623982135038676243268957 = 5491109461 * 44911984678816264937\n",
      "29 -th\n",
      "221688211550448625490808871099\n",
      "full time 4.71312952041626 [s]\n",
      "Ans: 221688211550448625490808871099 = 3224334847 * 68754711303236002117\n",
      "30 -th\n",
      "880260187382279664798627022433\n",
      "full time 4.706533908843994 [s]\n",
      "Ans: 880260187382279664798627022433 = 99888605911043844859 * 8812418387\n",
      "31 -th\n",
      "184848282517166409820694721437\n",
      "32 -th\n",
      "77218440559375974408592846333\n",
      "full time 4.512877702713013 [s]\n",
      "Ans: 77218440559375974408592846333 = 1926202193 * 40088439749469215981\n",
      "33 -th\n",
      "90129102670229201933067558419\n",
      "full time 4.661862850189209 [s]\n",
      "Ans: 90129102670229201933067558419 = 1570857601 * 57375730691854864019\n",
      "34 -th\n",
      "177811105193671809539440590619\n",
      "full time 4.697584867477417 [s]\n",
      "Ans: 177811105193671809539440590619 = 8068587533 * 22037451346525759943\n",
      "35 -th\n",
      "460136951685899351098996143107\n",
      "36 -th\n",
      "728902502381674223630741707139\n",
      "37 -th\n",
      "455617203969272617898508718291\n",
      "38 -th\n",
      "162953482442215967975061106081\n",
      "39 -th\n",
      "78946909995924901156756818971\n",
      "full time 4.463083505630493 [s]\n",
      "Ans: 78946909995924901156756818971 = 2400749999 * 32884269511114931029\n",
      "40 -th\n",
      "379196556719389516917141879341\n",
      "41 -th\n",
      "390534213167454130471107127547\n",
      "full time 4.423370361328125 [s]\n",
      "Ans: 390534213167454130471107127547 = 6943499119 * 56244583094827081013\n",
      "42 -th\n",
      "300577444519655585288331045601\n",
      "full time 4.620010614395142 [s]\n",
      "Ans: 300577444519655585288331045601 = 66472245229887273697 * 4521848833\n",
      "43 -th\n",
      "301455263128005525281474467927\n",
      "44 -th\n",
      "444789297574607141613241097213\n",
      "full time 4.454719305038452 [s]\n",
      "Ans: 444789297574607141613241097213 = 4600572913 * 96681284263042641101\n",
      "45 -th\n",
      "343483422602226664091427434401\n",
      "46 -th\n",
      "129867996109315406660839973021\n",
      "full time 4.6646568775177 [s]\n",
      "Ans: 129867996109315406660839973021 = 2718741029 * 47767696416853319449\n",
      "47 -th\n",
      "302146655214193869351886212113\n",
      "48 -th\n",
      "226457771766302792588021057807\n",
      "full time 4.440407752990723 [s]\n",
      "Ans: 226457771766302792588021057807 = 2506223509 * 90358170750964251923\n",
      "49 -th\n",
      "140041641098423502781743985763\n",
      "full time 4.633544683456421 [s]\n",
      "Ans: 140041641098423502781743985763 = 1679187569 * 83398450348118020627\n",
      "50 -th\n",
      "292415882066083111321612310239\n",
      "51 -th\n",
      "709155617740838693555689129931\n",
      "52 -th\n",
      "245987763976360771050351365723\n",
      "full time 4.6535115242004395 [s]\n",
      "Ans: 245987763976360771050351365723 = 2779196011 * 88510404808709539793\n",
      "53 -th\n",
      "380447891865298630739742474533\n",
      "54 -th\n",
      "126235935793435723850928218629\n",
      "55 -th\n",
      "634636296079931928870605754419\n",
      "full time 4.436200380325317 [s]\n",
      "Ans: 634636296079931928870605754419 = 8171389019 * 77665656916380366601\n",
      "56 -th\n",
      "258507033361845400243072308379\n",
      "full time 4.454535007476807 [s]\n",
      "Ans: 258507033361845400243072308379 = 5931475441 * 43582247947108275019\n",
      "57 -th\n",
      "400979572207858393963691904607\n",
      "full time 4.6135876178741455 [s]\n",
      "Ans: 400979572207858393963691904607 = 4374956981 * 91653374867289556547\n",
      "58 -th\n",
      "153385471598239479577384032727\n",
      "59 -th\n",
      "265513283813856600199825645367\n",
      "full time 4.3686299324035645 [s]\n",
      "Ans: 265513283813856600199825645367 = 4730915141 * 56123028188100954187\n",
      "60 -th\n",
      "856379455494171936966656720501\n",
      "full time 4.430401086807251 [s]\n",
      "Ans: 856379455494171936966656720501 = 9691058551 * 88367999325089614451\n",
      "61 -th\n",
      "55919497765722418041961401059\n",
      "62 -th\n",
      "470201190277946433404893520017\n",
      "63 -th\n",
      "769587062099604751022311560319\n",
      "64 -th\n",
      "419346007586632311115799799059\n",
      "full time 4.445438623428345 [s]\n",
      "Ans: 419346007586632311115799799059 = 7089801541 * 59147777996545236599\n",
      "65 -th\n",
      "834290240700443108426279159953\n",
      "full time 4.457149505615234 [s]\n",
      "Ans: 834290240700443108426279159953 = 9021491249 * 92478085681557491297\n",
      "66 -th\n",
      "125452430227149557089252426261\n",
      "67 -th\n",
      "113411143747223830114303941523\n",
      "68 -th\n",
      "641034510322596802356116956643\n",
      "full time 4.590188503265381 [s]\n",
      "Ans: 641034510322596802356116956643 = 8330449307 * 76950772605259285849\n",
      "69 -th\n",
      "347778846767706801544458160381\n",
      "70 -th\n",
      "464368862469049156870789169633\n",
      "full time 4.453603029251099 [s]\n",
      "Ans: 464368862469049156870789169633 = 7683850949 * 60434392279496721517\n",
      "71 -th\n",
      "160211739869231430342313248533\n",
      "full time 4.6448376178741455 [s]\n",
      "Ans: 160211739869231430342313248533 = 6325418221 * 25328244595327830473\n",
      "72 -th\n",
      "187569961792660374075791004259\n",
      "73 -th\n",
      "212810280197059958588857826117\n",
      "full time 4.45659327507019 [s]\n",
      "Ans: 212810280197059958588857826117 = 9881408221 * 21536432402903351177\n",
      "74 -th\n",
      "386349299789348240801920546057\n",
      "75 -th\n",
      "440410308829349021117228083549\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "76 -th\n",
      "171691324072243976834295667343\n",
      "full time 4.733232259750366 [s]\n",
      "Ans: 171691324072243976834295667343 = 2409800069 * 71247123892519058947\n",
      "77 -th\n",
      "134101163897703149139958755851\n",
      "78 -th\n",
      "97651528337720191853061204619\n",
      "full time 4.68199348449707 [s]\n",
      "Ans: 97651528337720191853061204619 = 1036529119 * 94210115806423564501\n",
      "79 -th\n",
      "421667819170003969481109629651\n",
      "full time 4.390970230102539 [s]\n",
      "Ans: 421667819170003969481109629651 = 6638223751 * 63521182018982530901\n",
      "80 -th\n",
      "355032056146684656818470964357\n",
      "full time 4.654649257659912 [s]\n",
      "Ans: 355032056146684656818470964357 = 7206273197 * 49267082504516468281\n",
      "81 -th\n",
      "75178712832276951506735973281\n",
      "82 -th\n",
      "53322962613929951478028956163\n",
      "83 -th\n",
      "123669299735530348997054563007\n",
      "full time 4.525863170623779 [s]\n",
      "Ans: 123669299735530348997054563007 = 4326984593 * 28580942935548453199\n",
      "84 -th\n",
      "143968533959816203250218661023\n",
      "85 -th\n",
      "241888720956264528860844819373\n",
      "86 -th\n",
      "312618273510524184863957991761\n",
      "pq\n",
      "87 -th\n",
      "731978832122579837255795346313\n",
      "88 -th\n",
      "99620041756833586555342019221\n",
      "full time 4.583600044250488 [s]\n",
      "Ans: 99620041756833586555342019221 = 1366285111 * 72913069867182053011\n",
      "89 -th\n",
      "700179220249508597303465172779\n",
      "full time 4.572116136550903 [s]\n",
      "Ans: 700179220249508597303465172779 = 9913840943 * 70626432709099859653\n",
      "90 -th\n",
      "172182739715500301620198882121\n",
      "91 -th\n",
      "278126032378894518623684662037\n",
      "full time 4.5838463306427 [s]\n",
      "Ans: 278126032378894518623684662037 = 8185226681 * 33979026265026479677\n",
      "92 -th\n",
      "497047991059771480344859197227\n",
      "93 -th\n",
      "120535823246444399262395809529\n",
      "full time 4.7893078327178955 [s]\n",
      "Ans: 120535823246444399262395809529 = 1495110511 * 80620009263278063639\n",
      "94 -th\n",
      "309629047404776248767164744207\n",
      "pq\n",
      "95 -th\n",
      "303924936640025186701906052053\n",
      "96 -th\n",
      "334786669907324601361702666699\n",
      "full time 4.488482236862183 [s]\n",
      "Ans: 334786669907324601361702666699 = 5558810363 * 60226316072175855473\n",
      "97 -th\n",
      "68570481677999934582279632569\n",
      "full time 4.184496879577637 [s]\n",
      "Ans: 68570481677999934582279632569 = 5260657663 * 13034583519904654663\n",
      "98 -th\n",
      "97410289840556290127664800557\n",
      "full time 4.339517116546631 [s]\n",
      "Ans: 97410289840556290127664800557 = 8637416209 * 11277711700294919773\n",
      "99 -th\n",
      "255565981658848665798873800693\n",
      "full time 4.654656887054443 [s]\n",
      "Ans: 255565981658848665798873800693 = 3223768897 * 79275528061789804469\n",
      "100 -th\n",
      "716026150443765483151306706501\n",
      "full time 4.622949838638306 [s]\n",
      "Ans: 716026150443765483151306706501 = 9122712857 * 78488291988095124493\n",
      "53 factorized!\n",
      "average time 4.51382451687219 [s]\n",
      "full time for factorization: 277.7336759567261 [s]\n",
      "53.0 % succeed\n",
      "FIN\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "from sympy.ntheory.generate import randprime\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",
    "nlist=[]\n",
    "sample=100\n",
    "for i in range(1,sample+1):\n",
    "    a=randprime(10**9,10**10)\n",
    "    b=randprime(10**19,10**20)\n",
    "    nn=a*b\n",
    "    nlist.append(nn)\n",
    "\n",
    "textnp=input('the number of primes:')\n",
    "np=int(textnp)\n",
    "textalpha=input('power:')\n",
    "alpha=int(textalpha)\n",
    "textmaxx=input('maxx:')\n",
    "maxx=int(textmaxx)\n",
    "\n",
    "\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",
    "plist2310=[]\n",
    "cplist2310=[]\n",
    "\n",
    "print('N=',N)\n",
    "print('π(N)=',countp)\n",
    "\n",
    "prim=primorial(np,pplist)\n",
    "pplist=[]\n",
    "k=pow(prim,alpha)\n",
    "ff=time.time()\n",
    "pret=ff-sf\n",
    "print('full time',pret,'[s]')\n",
    "\n",
    "delta=0.1\n",
    "count=0\n",
    "clear=0\n",
    "t=0\n",
    "for n in nlist:\n",
    "    count+=1\n",
    "    sf=time.time()\n",
    "    print(count,'-th')\n",
    "    print(n)\n",
    "    percent=0\n",
    "    g=1\n",
    "    xx=1\n",
    "    BOOL=False\n",
    "    BOOLpq=True\n",
    "    BOOLfirst=True\n",
    "    x=prim\n",
    "    xx=1\n",
    "    for x0 in range(1,maxx+1):\n",
    "        if BOOL:\n",
    "            break\n",
    "#        if x0/maxx>percent:\n",
    "#            print(round(percent*100,2),'%')\n",
    "#            percent+=delta\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",
    "                clear+=1\n",
    "                t+=ff-sf\n",
    "                break\n",
    "\n",
    "print(clear,'factorized!')\n",
    "print('average time',t/clear,'[s]')\n",
    "print('full time for factorization:',pret+t,'[s]')\n",
    "print(round(clear/sample*100.0,2),'% succeed')\n",
    "print('FIN')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}