primes.janet

(use spork/test)
(use spork/misc)
(use spork/math)

(def- small-primes
  "primes less than 212"
  [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 107 109 113 127 131 137 139 149 151
   157 163 167 173 179 181 191 193 197 199 211])

(def- soe-indices
  "pre-calced sieve of eratosthenes for 2 3 5 7"
  [1 11 13 17 19 23 29 31 37 41 43 47
   53 59 61 67 71 73 79 83 89 97 101 103
   107 109 113 121 127 131 137 139 143 149 151 157
   163 167 169 173 179 181 187 191 193 197 199 209])

(def- soe-offsets
  "distances between sieve values"
  [10 2 4 2 4 6 2 6 4 2 4 6
   6 2 6 4 2 6 4 6 8 4 2 4
   2 4 8 6 4 6 2 4 6 2 6 6
   4 2 4 6 2 6 4 2 4 2 10 2])

(def- soe-table
  "tabulated offsets mod 105"
  [0 10 2 0 4 0 0 0 8 0 0 2 0 4 0
   0 6 2 0 4 0 0 4 6 0 0 6 0 0 2
   0 6 2 0 4 0 0 4 6 0 0 2 0 4 2
   0 6 6 0 0 0 0 6 6 0 0 0 0 4 2
   0 6 2 0 4 0 0 4 6 0 0 2 0 6 2
   0 6 0 0 4 0 0 4 6 0 0 2 0 4 8
   0 0 2 0 10 0 0 4 0 0 0 2 0 4 2])

(def- rm-bases-32
  "bases for rabin-miller determinism to 2^32"
  [2 7 61])

(def- rm-bases-64
  "bases for rabin-miller determinism to 2^64"
  [2 325 9375 28178 450775 9780504 1795265022])

(def- prime-prods
  #(* ;(take 13 small-primes))
  304250263527210)

(defn rabin-miller-prp?
  [n & bases]
  (def ps
    (if (empty? bases)
      (if (int? n) rm-bases-32 rm-bases-64)
      bases))
  (var d (- n 1))
  (var s 0)
  (while (zero? (mod d 2))
    (++ s)
    (set d (div d 2)))
  (label result
    (each p ps
      (var x (powmod p d n))
      (when (compare< 1 x (- n 1))
        (for r 1 s
          (set x (mulmod x x n))
          (if-not (compare< 1 x (- n 1)) (break)))
        (if-not (compare= x (- n 1))
          (return result false))))
    true))

(defn prime?
  [n]
  (cond
    (compare<= n 211) (do
                        (def m (binary-search n small-primes compare<))
                        (compare= n (in small-primes m)))
    (= 0 (jacobi n prime-prods)) false
    (rabin-miller-prp? n)))

(defn next-prime
  "Returns the next prime number strictly larger than `n`."
  [n]
  (label result
    (def x (+ n 1))
    (if (compare<= x 2) (return result 2))
    (when (compare<= x 211)
      (def m (binary-search x small-primes compare<))
      (return result (in small-primes m)))
    (def j (mod x 210))
    (def m (binary-search j soe-indices compare<))
    (var i (+ x (- (in soe-indices m) j)))
    (def offs [;(slice soe-offsets m) ;(slice soe-offsets 0 m)])
    (forever
      (each o offs
        (if (prime? i)
          (return result i))
        (+= i o)))))

(defn primes
  "A boundless prime number generator."
  []
  (coro
    (each n small-primes (yield n))
    (def sieve @{221 13 253 11})
    (def pg (drop 6 (primes)))
    (var p (resume pg))
    (var q (* p p))
    (var n 211)
    (forever
      (each offset soe-offsets
        (+= n offset)
        (def stp (get sieve n))
        (cond
          stp (do
                (put sieve n nil)
                (var nxt (div n stp))
                (+= nxt (in soe-table (mod nxt 105)))
                (while (get sieve (* nxt stp))
                  (+= nxt (in soe-table (mod nxt 105))))
                (put sieve (* nxt stp) stp))
          (< n q) (yield n)
          (do
            (put sieve (+ q (* p (in soe-table (mod p 105)))) p)
            (set p (resume pg))
            (set q (* p p))))))))

(do
  "tests"

  (defn trial-division
    [n]
    (cond
      (< n 2) false
      (= n 2) true
      (= 0 (mod n 2)) false
      (label result
        (var p 3)
        (while (<= (* p p) n)
          (if (= 0 (mod n p)) (return result false))
          (+= p 2))
        true)))

  (def big-primes
    [100123456789
     100529784361
     101103163367
     101107157131
     101111111111
     101234567897
     101601701401
     101740496633
     103723971119
     105840677923
     107928278317
     108280301737
     109297270343
     109661199601
     111160669681
     111161191111
     111417192023
     111696081881
     112346958007
     113013596393
     113131311401
     113391385603
     115829122963
     118116011609
     118233435679
     119218851371
     121392937879
     123462985007
     123511311277
     124567987631
     125411328001
     126704222713
     127397154761
     129866728583
     130147795189
     131681894401
     131707310437
     134141142143
     136363636361
     137168442221
     137438691329
     137438953481
     139149151157
     141516182021
     141592653589
     142112242123
     142356474523
     142915724779
     143014298809
     145679876431
     150614187107
     152164007921
     157119131933
     158033851523
     162536496481
     162849681287
     166400805323
     166425493681
     166425813649
     166661866681
     168409140869
     171190210231
     171727482881
     172573565537
     181030208131
     183208285259
     186125268239
     188886809101
     189686906191
     189795640003
     191198888863
     191373251117
     194036151289
     196719631961
     198765432101
     200560490131
     201820192019
     205235235391
     220123456789
     220999999999
     232911191713
     235375676171
     239651440411
     248857367251
     251117233141
     252097800623
     255255255251
     255339610381
     255339670841
     257778788987
     260389232731
     262364233421
     274860381259
     275311670611
     277535577223
     285311670733
     293826343073
     298999999999
     308457624821
     313191181151
     313473008141
     315569251763
     316234143227
     323866659173
     328628315459
     333227777777
     333332333333
     334473276937
     337016056721
     342054335261
     344980016453
     351725765537
     352573616771
     353373727757
     355323522737
     355711131719
     357315397211
     358729059641
     381654729067
     393142151459
     411379717319
     415926535897
     433123191173
     445317119867
     454280348267
     454935396569
     463479467461
     483148266971
     507995698619
     512463676147
     526858348381
     539423223413
     542939080319
     547716131821
     548535559133
     553559562581
     555553332211
     555555555551
     555555577777
     576529484441
     581485876661
     582017570143
     597325496783
     608888888809
     608981813029
     619010109889
     619737131179
     635365536563
     655372571753
     655373525717
     657835997711
     661991890601
     662626111933
     665545362821
     666666555551
     674960891221
     676703534071
     689101181569
     698908090691
     700123456789
     701234567897
     737797911337
     744509905409
     753352617167
     753676171253
     757777777777
     762394144181
     762939453127
     765430123567
     774004377953
     777775777777
     816425361649
     824633702441
     825353008489
     837973716761
     902659997773
     908209935089
     921023456789
     964991203151
     976543312183
     977973373171
     978058181203
     981563119939
     999998999999
     999999000001
     1000000000039
     1000000000063
     1000000001159
     1000000002217
     1000000999999
     1000008000001
     1000123457689
     1000123465987
     1012345678901
     1012346665879
     1024688864201
     1050100100501
     1078834318169
     1099511628401
     1100011100011
     1110110110111
     1110111110111
     1111111999999
     1111118111111
     1111120211111
     1116295198451
     1118810161681
     1123529253211
     1131313515313
     1133328809969
     1146890986411
     1161468891953
     1161880189181
     1169769749219
     1196980996691
     1218131412181
     1226280710981
     1231507051321
     1252099518401
     1312961745803
     1344409044431
     1346140268867
     1349623494409
     1398023584459
     1428571758241
     1431535622177
     1468986414689
     1481754620933
     1486287894323
     1497631652873
     1534139560403
     1534696030979
     1537267083749
     1597233891353
     1606081806061
     1616110116161
     1618033308161
     1618033988749
     1625800359439
     1666666666661
     1686910196861
     1719004000057
     1732565537257
     1818116091619
     1835211125381
     1886881868881
     1888081808881
     1888691180161
     1906101090199
     1915318120519
     1918960000861
     1919110119191
     1988006860681
     2004006004001
     2090609914951
     2328316694653
     2335557777577
     2351123294153
     2651541199513
     2705863197041
     2748779069441
     2760889966651
     2822916096001
     2999999899999
     3059220303001
     3111111111113
     3192202523137
     3238428376721
     3273534353723
     3278744415797
     3484606209571
     3525357323233
     3531577135439
     3571113171931
     3651980735243
     3664533202453
     3763863863761
     3889108085627
     4016465016163
     4398042316799
     4615392897979
     4643668177711
     4666666666667
     4913685912167
     5237732522753
     5298696301807
     5335039446259
     5352640789913
     5510987654321
     5555555555551
     5599297703999
     5783272917893
     5942636062289
     6056529316217
     6123456789101
     6123584726269
     6435409832617
     6440261849537
     6660000000001
     6746328388801
     6987191424553
     7073313533333
     7142857142857
     7177111117717
     7184500054817
     7284717174827
     7625597485003
     7666466646667
     7762868682677
     7777774777777
     7777775552353
     7929188600987
     8212668876301
     8284590452353
     8313667333393
     8401414020133
     9095665192937
     9203225223029
     9740985827329
     9876543244501
     9977770001777
     9999919199999
     9999991111111
     9999999998987
     10000000000283
     10006181886601
     10011111122113
     10012345678901
     10102323454577
     10110111011111
     10861196119801
     10987654321001
     11091501631241
     11108452651921
     11111333333333
     11236129794797
     11376747235397
     11410337850553
     12326713558771
     12345678976541
     12345678987431
     12456898765321
     12702232868389
     12966235728587
     13172937415361
     13301522971817
     13334390952317
     13791315212531
     14014014014159
     14444999999999
     15154262241479
     15261281789861
     15275163131153
     15307263442931
     15423094826093
     16000611609061
     18197520028579
     18285670562881
     18640889198609
     18691113008663
     18826507658281
     19489355557003
     19981091998181
     20215043836789
     20325153628489
     20479999999999
     20991129234731
     21732382677641
     22333555577777
     23513892331597
     24738041398529
     27064032706411
     27292996856087
     27985032798461
     28116440335967
     28722900390631
     28862180229031
     28862180229121
     28999134198739
     29065965967667
     29202114663949
     29313741434753
     29475832947601
     29996224275833
     32267562876001
     32353461605953
     33670369817243
     34127252370851
     34445333343437
     34524689549219
     35557777777987
     35711101131151
     35795175733399
     37383940414243
     38332212254719
     39153010938487
     41434547495153
     43308631298509
     45678910111213
     47101299815623
     50000010000001
     52529393474711
     55555544444441
     57757791939599
     58550453144611
     58575551494639
     59616771737983
     60000000000013
     60111111111109
     60419650387267
     60818091990661
     62481801147341
     63604045061911
     67280421310721
     68289980006401
     69010616901091
     69747782858687
     73275315729173
     73716967656361
     73727170696867
     74596893730427
     75022592087629
     78456580281239
     79012338765433
     81744303091421
     83695120256591
     86812553978993
     87255058923913
     88343532313733
     88888888888889
     88929267773197
     89637484042681
     89888786858483
     90442568793803
     92200000000001
     93917775575551
     97012345678979
     97797371371331
     99999999944441
     100000000105583
     100033000330001
     100110101011001
     100352695899791
     101012345678789
     101012345678989
     101103107109113
     101103107109307
     101741582076581
     105010123456789
     105120615024773
     106111115118119
     106800081666611
     109139149179199
     111111151111111
     116315256993601
     116666666666611
     119315717513911
     119755797430727
     122243323466323
     122334444555553
     123123454321321
     123456136101521
     123456789101213
     123456797654321
     123467898764321
     123571113171923
     125216512343729
     131175323571113
     134567897654321
     135791113151719
     139239739439839
     140737488356207
     141616531685159
     144121100816449
     145661743208479
     146263628637547
     147625901476283
     151515151515151
     166986101689661
     170669145704411
     176860696068671
     181395559296673
     182697604666543
     189811909119191
     190296921999337
     191373383373191
     192549818945291
     197198199200201
     199689672115897
     231917131175321
     233444000011111
     253931039382791
     264575131106459
     274988895429719
     275604952420573
     277777788888989
     278801239404553
     281474993487871
     291598227841757
     302875106592241
     303160419086407
     307031012708191
     309427398372577
     310950284569927
     311111111111113
     313353373353313
     318532111235813
     320255973501901
     324578696875423
     333333373333333
     333555577577777
     344555666677777
     347811194367163
     348413484334847
     355693655479801
     399899999999999
     409881449991499
     440653748357699
     468395662504823
     484511389338941
     485398038695407
     493935332521159
     518463576809201
     535006138814359
     555554444332213
     578415690713087
     597655503030737
     666666666666631
     688846502588399
     691096906169011
     727777887889889
     733709701389359
     736353433323133
     737373737373737
     766788787887667
     777737777777777
     777773333999551
     777777355553753
     777777715963511
     789012345678901
     799333555511111
     809709509409109
     810000006707603
     870530414842019
     888888877777777
     889292677731979
     914148152112161
     923291713111753
     930348707843039
     953467954114363
     973369606963379
     977555333311111
     979853562951413
     980835832582657
     987654321346789
     988666444411111
     990377764891511
     999888866553221
     999998727899999
     1000000000100011
     1003229774283941
     1011001110001111
     1084051191974761
     1086868110868699
     1090109110921093
     1106098069699111
     1111235916285193
     1181118711931201
     1208152477719361
     1211221211212211
     1235711131175321
     1238926361552897
     1255571292290713
     1301477951890177
     1311753223571113
     1311870831664661
     1333333333333333
     1379131521253133
     1391098979592919
     1423214346574567
     1510553619999637
     1593350922240001
     1609161918110111
     1616668118999191
     1657688103077659
     1680588011350901
     1693182318746371
     1737476797107127
     1867357583296451
     1886999912279359
     1889080110806881
     1989530586646177
     1990474529917009
     2035802523820057
     2067078579454279
     2222226095589337
     2231588810593399
     2345678911111111
     2355457523880889
     2357275332573527
     2357353373727757
     2380072466365871
     2468642135797531
     2573253757232573
     2744337540964913
     2828074326968519
     2856646544865959
     2956667885147129
     3129313031303131
     3325997869054417
     3391382115599173
     3637383940414243
     3733799929399999
     3931520917431241
     3940518300860411
     4429978144299823
     4444280714420857
     4547495153555759
     4564564564564561
     4847464544434241
     5111111111111119
     5944066965503999
     5953474341373129
     5999999999899999
     6171054912832631
     6241156164232441
     6435616333396997
     6664666366626661
     6735249118018991
     6988699669998001
     7005264275346131
     7190597297273099
     7523725352733257
     7753757725325377
     7897466719774591
     7897897897897897
     8008808808808813
     8343656381177203
     8690333381690951
     8778405442862239
     9007199254740847
     9007199254740881])

  (def bigger-primes
    ["9293787934331213"
     "9436835835813811"
     "9779737137133111"
     "9949370777987917"
     "9999999900000001"
     "10000000002065383"
     "10106099866009181"
     "10112269203786181"
     "10234567876543201"
     "10269797835402631"
     "10939058860032031"
     "10968523783746901"
     "11018881818881011"
     "11120933330250889"
     "11333555557777777"
     "11417969834487023"
     "12223242526272829"
     "12348516587712457"
     "12962962592588887"
     "13000000000000019"
     "13107181911273173"
     "13173779397737131"
     "13176245766932173"
     "13311464115101051"
     "13457986268975431"
     "13661181333262459"
     "13666666666666613"
     "13666666666666631"
     "15125111011152151"
     "15795210542132999"
     "17000000000000071"
     "19019684767739993"
     "19149376019158129"
     "19611091991096119"
     "22222223333355757"
     "22263490219831439"
     "22439962446379651"
     "23456789101112123"
     "27714215764134587"
     "30000006160000003"
     "31896090547101491"
     "32494189635056477"
     "33334444777777777"
     "33832795028841971"
     "36028797018963913"
     "37033804397792473"
     "37124508045065437"
     "43142746595714191"
     "44444446666688899"
     "47784853865664217"
     "55350776431903243"
     "55453628211510631"
     "55555555555555999"
     "59604644783353249"
     "59649589127497217"
     "66555444443333333"
     "66606660666066601"
     "69668002914515347"
     "70000006660000007"
     "71117012721071117"
     "71828182828182817"
     "74747474747474747"
     "77777777977777777"
     "81615141210198641"
     "91521253335394951"
     "94350482728405349"
     "97654321012345679"
     "98764321012345789"
     "98765321012456789"
     "98765432101456789"
     "98823199699242779"
     "99194853094755497"
     "99999988898898889"
     "99999999999899999"
     "99999999999999997"
     "100109100129100151"
     "102598800232111471"
     "111101234567891111"
     "113127131137139149"
     "115578717622022981"
     "117116115114112111"
     "124277066894534299"
     "137153163127255511"
     "139717391739171397"
     "147578905723456789"
     "153722867280912929"
     "159067808851610657"
     "160409920439929091"
     "161111111111111111"
     "165678739293946997"
     "166667166667000003"
     "169177178183185187"
     "180811181061181081"
     "191128877173556587"
     "212345678987654321"
     "220724578848317699"
     "222222222222222221"
     "222333555557777777"
     "255455445544554553"
     "261798184036870849"
     "277233211975331753"
     "280743771536011781"
     "300000224101777931"
     "302301299298295291"
     "311172329414761211"
     "316227766016837933"
     "333333331241623291"
     "352521223451364323"
     "356112891082412207"
     "359681422627177289"
     "369121518212427307"
     "421538917598915629"
     "443231282319131071"
     "444444666868899899"
     "449317973725128511"
     "496481100121144169"
     "581321345589144233"
     "599999999999899999"
     "611091996016611019"
     "618681508598750923"
     "618819619619660099"
     "666666555557777777"
     "707274757677788081"
     "777777722155555333"
     "789795449254776509"
     "909090909090909091"
     "953947941937929919"
     "973006384792642181"
     "974383618913296759"
     "986143414027351997"
     "989466010702279111"
     "1000000000000000003"
     "1000000000000000009"
     "1010203040506070809"
     "1010999888887777777"
     "1011112131415161719"
     "1018264464644628101"
     "1023456987896543201"
     "1023458697968543201"
     "1023489657569843201"
     "1023975468645793201"
     "1023985674765893201"
     "1029001476404750269"
     "1034578692968754301"
     "1034725698965274301"
     "1056208858880824379"
     "1109011810160101609"
     "1111001101011001111"
     "1111111111111111111"
     "1111111111111111417"
     "1111111112345679001"
     "1111918171614101513"
     "1111918171614121013"
     "1119416189101109149"
     "1122334455667788991"
     "1147797409030815779"
     "1182932213481679513"
     "1234567654321234567"
     "1234567894987654321"
     "1241111124211111421"
     "1294584340434854921"
     "1341351362137138139"
     "1425172824437699411"
     "1524157875019052101"
     "1618964990108856391"
     "1640293473202755797"
     "1712329866165608783"
     "1732050807568877293"
     "1799999999999999999"
     "1801241230056600523"
     "1971179391939711791"
     "1981856124216581891"
     "2015121110987654321"
     "2223243435546756677"
     "2305843009213693951"
     "2305843011361841323"
     "2327074306453592351"
     "2445566867868888899"
     "2999998999999999999"
     "3203000719597029781"
     "3294760066632959081"
     "3319393725273939133"
     "3331113965338635107"
     "3399714628553118049"
     "3441173392933731913"
     "3842148274728412483"
     "3868168229228618683"
     "3874204890000000001"
     "4968487560233624827"
     "5449909581264135103"
     "5555555555555555533"
     "6082394749206781697"
     "6284968128335503367"
     "6351332252927568989"
     "6568408355712890627"
     "6787988999657777797"
     "7393913311133193937"
     "7532753275327532753"
     "7654321012345678987"
     "8093914354023690019"
     "8223335555577777779"
     "8230452606740808761"
     "8512677386048191063"
     "8888888897888888899"
     "9181531581341931811"])

  (def big-pseudoprimes
    [1373653
     1530787
     1987021
     2284453
     3116107
     5173601
     6787327
     11541307
     13694761
     15978007
     16070429
     16879501
     25326001
     27509653
     27664033
     28527049
     54029741
     61832377
     66096253
     74927161
     80375707
     101649241
     161304001
     960946321
     1157839381
     3215031751
     3697278427
     5764643587
     6770862367
     14386156093
     15579919981
     18459366157
     19887974881
     21276028621
     27716349961
     29118033181
     37131467521
     41752650241
     42550716781
     43536545821
     118670087467
     307768373641
     315962312077
     354864744877
     457453568161
     528929554561
     546348519181
     602248359169
     1362242655901
     1871186716981
     2152302898747
     2273312197621
     2366338900801
     3343433905957
     3461715915661
     3474749660383
     3477707481751
     4341937413061
     4777422165601
     5537838510751])

  (def jacobi-tests
    [0 1 1
     0 585213579152349 0
     8 6720259138994321 1
     4 3529872439860193 1
     1 8865951665456613 1
     2 3751179396445577 1
     3 8857077568716611 1
     5 6724496004486515 0
     6 8046472257518507 -1
     7 1018578125212317 -1
     2883827 176912159547505 0
     28247691 946201408616763 0
     19708837 522602379673365 0
     13275491 879901654283069 0
     60217093 5240865403156329 0
     47257397 4366099047223353 0
     43746771 3450465360892371 0
     28218249 3334597467714585 0
     11487823 1239188652493365 0
     12927767599 8672338641 1
     60316482065 10376205733 1
     12718160572 40414256491 -1
     120812815652 231360065535 0
     117917744387 386108597301 -1
     1972212248293 500091801737 -1
     6182825798573 657084002447 -1
     7724453058855 4314999370589 1
     7587489170907 8474042507595 0
     9696584664327 8446084420521 0
     28511645797572 26659633033591 1
     51420282718547 82865707693791 1
     21704899141827 30086928426459 0
     488044769925626 1 1
     260979839748477 5 -1
     694655438452973 17 1
     207516837635459 5084893 0
     396249202456023 14136801 0
     121253238725769 94717919 0
     357644815400260 27389419382869 0
     114127918676057 223507053233071 1
     533840837447381 410811659094573 1
     444319204437207 407806165804965 0
     859875223300786 587409117327703 0
     458664366106310 542012645716555 0
     424471304525198 2351874079908277 1
     557014689515323 1335410288492449 0
     153451963855887 1791234085341119 0
     7601489827875349 3 1
     2448829697631485 9 1
     6402808835167554 7 -1
     8658574414874615 15 0
     3057215490220020 11 -1
     3667924217114464 13 -1
     1636349321668428 67995153 0
     3468280965012603 133198631 0
     3447863313944205 127231715 0
     4774734459975410 107930263 0
     4508174835245718 114427053 0
     4341041231878004 107549279 0
     5914682029309478 4561197873371 1
     2592183347075284 6758805834169 1
     8119957211750944 81950119387153 -1
     3928288016132477 47031755147963 -1
     1567497221445441 676271573590573 1
     3849432154013499 124197603917203 1
     8989478004945231 813421418837009 1
     2352560480455240 546175802817609 0
     1397775408790930 301656063758065 0
     7300132779063743 923821524336799 -1
     2172713837802427 736479480290711 -1
     1168603720789234 7699546778746913 1
     2323469328644027 2276564181584985 1
     4560278553513941 3783685953479921 1
     6596617150158661 5927630295508915 1
     6385868191676153 4426089584466073 1
     8723741114301869 1559345136119577 1
     4622568476421908 4170463869060991 1
     7126749286305196 6439298346766197 1
     6307994731864734 3488208932992171 1
     2292810700693211 8152126868198791 1
     5615410673045322 4869530827612931 1
     7452335230932670 2019154359110699 1
     5130615933238582 2882556393517377 1
     3525582389132045 3515179569082871 1
     3845922998562750 1825997838443061 0
     3933618783354591 5378276440500211 0
     3851405698358413 4880238089886453 0
     5878988890756469 2861006357180511 0
     8874876052301087 6136905421930341 0
     1435091917964529 2898547151934585 0
     6680479536006686 1853547664257451 -1
     3833863307507711 1780254117051967 -1
     1437351394353646 1828705433408745 -1
     1922007955867708 1255085380091051 -1
     6837057651372637 5930513687511503 -1
     8855677375508641 7328760412908381 -1
     3387748941432134 8519439313817431 -1
     3550609424633387 1840750301656275 -1])

  (def pg (take 10000 (primes)))
  (timeit-loop [p :in pg] (assert (prime? p) (string "prime " p)))
  (assert (= 104729 (last pg)) "10000th prime")

  (assert (all = (map next-prime pg) (drop 1 pg)) "next-prime")

  (for n 1 100000
    (assert (= (trial-division n) (prime? n)) n))

  (assert (all (fn [[a m o]] (= (jacobi a m) o)) (partition 3 jacobi-tests)) "jacobi")

  (timeit-loop [p :in big-primes] (assert (prime? p) (string "big primes " p)))
  (timeit-loop [p :in (map int/s64 big-primes)] (assert (prime? p) (string "big primes s64 " p)))
  (timeit-loop [p :in (map int/s64 bigger-primes)] (assert (prime? p) (string "bigger primes s64 " p)))
  (timeit-loop [p :in (map int/u64 bigger-primes)] (assert (prime? p) (string "bigger primes u64 " p)))

  (assert (all |(rabin-miller-prp? $ 2 3) big-pseudoprimes) "big pseudoprimes base 2 3")
  (assert (not (some rabin-miller-prp? big-pseudoprimes)) "big pseudoprimes rabin-miller"))