OI 质数表

博主： Zi_Gao
发布时间：2024 年 07 月 17 日
672 次浏览
暂无评论
14036字数
分类： OI

## $[10^2,10^6]$

| 1e2 | 1e3  | 1e4   | 1e5    | 1e6     |
| ----- | ------ | ------- | -------- | --------- |
| 101 | 1009 | 10007 | 100003 | 1000003 |
| 103 | 1013 | 10009 | 100019 | 1000033 |
| 107 | 1019 | 10037 | 100043 | 1000037 |
| 109 | 1021 | 10039 | 100049 | 1000039 |
| 113 | 1031 | 10061 | 100057 | 1000081 |
| 127 | 1033 | 10067 | 100069 | 1000099 |
| 131 | 1039 | 10069 | 100103 | 1000117 |
| 137 | 1049 | 10079 | 100109 | 1000121 |
| 139 | 1051 | 10091 | 100129 | 1000133 |
| 149 | 1061 | 10093 | 100151 | 1000151 |
| 151 | 1063 | 10099 | 100153 | 1000159 |
| 157 | 1069 | 10103 | 100169 | 1000171 |
| 163 | 1087 | 10111 | 100183 | 1000183 |
| 167 | 1091 | 10133 | 100189 | 1000187 |
| 173 | 1093 | 10139 | 100193 | 1000193 |
| 179 | 1097 | 10141 | 100207 | 1000199 |
| 181 | 1103 | 10151 | 100213 | 1000211 |
| 191 | 1109 | 10159 | 100237 | 1000213 |
| 193 | 1117 | 10163 | 100267 | 1000231 |
| 197 | 1123 | 10169 | 100271 | 1000249 |
| 199 | 1129 | 10177 | 100279 | 1000253 |
| 211 | 1151 | 10181 | 100291 | 1000273 |
| 223 | 1153 | 10193 | 100297 | 1000289 |
| 227 | 1163 | 10211 | 100313 | 1000291 |
| 229 | 1171 | 10223 | 100333 | 1000303 |
| 233 | 1181 | 10243 | 100343 | 1000313 |
| 239 | 1187 | 10247 | 100357 | 1000333 |
| 241 | 1193 | 10253 | 100361 | 1000357 |
| 251 | 1201 | 10259 | 100363 | 1000367 |
| 257 | 1213 | 10267 | 100379 | 1000381 |
| 263 | 1217 | 10271 | 100391 | 1000393 |
| 269 | 1223 | 10273 | 100393 | 1000397 |
| 271 | 1229 | 10289 | 100403 | 1000403 |
| 277 | 1231 | 10301 | 100411 | 1000409 |
| 281 | 1237 | 10303 | 100417 | 1000423 |
| 283 | 1249 | 10313 | 100447 | 1000427 |
| 293 | 1259 | 10321 | 100459 | 1000429 |
| 307 | 1277 | 10331 | 100469 | 1000453 |
| 311 | 1279 | 10333 | 100483 | 1000457 |
| 313 | 1283 | 10337 | 100493 | 1000507 |
| 317 | 1289 | 10343 | 100501 | 1000537 |
| 331 | 1291 | 10357 | 100511 | 1000541 |
| 337 | 1297 | 10369 | 100517 | 1000547 |
| 347 | 1301 | 10391 | 100519 | 1000577 |
| 349 | 1303 | 10399 | 100523 | 1000579 |
| 353 | 1307 | 10427 | 100537 | 1000589 |
| 359 | 1319 | 10429 | 100547 | 1000609 |
| 367 | 1321 | 10433 | 100549 | 1000619 |
| 373 | 1327 | 10453 | 100559 | 1000621 |
| 379 | 1361 | 10457 | 100591 | 1000639 |

## $[10^7,10^{12}]$

| 1e7      | 1e8       | 1e9        | 1e10        | 1e11         | 1e12          |
| ---------- | ----------- | ------------ | ------------- | -------------- | --------------- |
| 10000019 | 100000007 | 1000000007 | 10000000019 | 100000000003 | 1000000000039 |
| 10000079 | 100000037 | 1000000009 | 10000000033 | 100000000019 | 1000000000061 |
| 10000103 | 100000039 | 1000000021 | 10000000061 | 100000000057 | 1000000000063 |
| 10000121 | 100000049 | 1000000033 | 10000000069 | 100000000063 | 1000000000091 |
| 10000139 | 100000073 | 1000000087 | 10000000097 | 100000000069 | 1000000000121 |
| 10000141 | 100000081 | 1000000093 | 10000000103 | 100000000073 | 1000000000163 |
| 10000169 | 100000123 | 1000000097 | 10000000121 | 100000000091 | 1000000000169 |
| 10000189 | 100000127 | 1000000103 | 10000000141 | 100000000103 | 1000000000177 |
| 10000223 | 100000193 | 1000000123 | 10000000147 | 100000000129 | 1000000000189 |
| 10000229 | 100000213 | 1000000181 | 10000000207 | 100000000171 | 1000000000193 |
| 10000247 | 100000217 | 1000000207 | 10000000259 | 100000000183 | 1000000000211 |
| 10000253 | 100000223 | 1000000223 | 10000000277 | 100000000193 | 1000000000271 |
| 10000261 | 100000231 | 1000000241 | 10000000279 | 100000000211 | 1000000000303 |
| 10000271 | 100000237 | 1000000271 | 10000000319 | 100000000223 | 1000000000331 |
| 10000303 | 100000259 | 1000000289 | 10000000343 | 100000000237 | 1000000000333 |
| 10000339 | 100000267 | 1000000297 | 10000000391 | 100000000253 | 1000000000339 |
| 10000349 | 100000279 | 1000000321 | 10000000403 | 100000000283 | 1000000000459 |
| 10000357 | 100000357 | 1000000349 | 10000000469 | 100000000319 | 1000000000471 |
| 10000363 | 100000379 | 1000000363 | 10000000501 | 100000000363 | 1000000000537 |
| 10000379 | 100000393 | 1000000403 | 10000000537 | 100000000367 | 1000000000543 |
| 10000439 | 100000399 | 1000000409 | 10000000583 | 100000000379 | 1000000000547 |
| 10000451 | 100000421 | 1000000411 | 10000000589 | 100000000393 | 1000000000561 |
| 10000453 | 100000429 | 1000000427 | 10000000597 | 100000000403 | 1000000000609 |
| 10000457 | 100000463 | 1000000433 | 10000000601 | 100000000411 | 1000000000661 |
| 10000481 | 100000469 | 1000000439 | 10000000631 | 100000000417 | 1000000000669 |
| 10000511 | 100000471 | 1000000447 | 10000000643 | 100000000427 | 1000000000721 |
| 10000537 | 100000493 | 1000000453 | 10000000649 | 100000000447 | 1000000000751 |
| 10000583 | 100000541 | 1000000459 | 10000000667 | 100000000487 | 1000000000787 |
| 10000591 | 100000543 | 1000000483 | 10000000679 | 100000000519 | 1000000000789 |
| 10000609 | 100000561 | 1000000513 | 10000000711 | 100000000567 | 1000000000799 |
| 10000643 | 100000567 | 1000000531 | 10000000723 | 100000000579 | 1000000000841 |
| 10000651 | 100000577 | 1000000579 | 10000000741 | 100000000621 | 1000000000903 |
| 10000657 | 100000609 | 1000000607 | 10000000753 | 100000000631 | 1000000000921 |
| 10000667 | 100000627 | 1000000613 | 10000000793 | 100000000637 | 1000000000931 |
| 10000687 | 100000643 | 1000000637 | 10000000799 | 100000000669 | 1000000000933 |
| 10000691 | 100000651 | 1000000663 | 10000000807 | 100000000699 | 1000000000949 |
| 10000721 | 100000661 | 1000000711 | 10000000877 | 100000000703 | 1000000000997 |
| 10000723 | 100000669 | 1000000753 | 10000000883 | 100000000721 | 1000000001051 |
| 10000733 | 100000673 | 1000000787 | 10000000889 | 100000000739 | 1000000001083 |
| 10000741 | 100000687 | 1000000801 | 10000000949 | 100000000747 | 1000000001123 |
| 10000747 | 100000717 | 1000000829 | 10000000963 | 100000000801 | 1000000001159 |
| 10000759 | 100000721 | 1000000861 | 10000000991 | 100000000817 | 1000000001197 |
| 10000763 | 100000793 | 1000000871 | 10000000993 | 100000000819 | 1000000001201 |
| 10000769 | 100000799 | 1000000891 | 10000000999 | 100000000861 | 1000000001213 |
| 10000789 | 100000801 | 1000000901 | 10000001041 | 100000000901 | 1000000001243 |
| 10000799 | 100000837 | 1000000919 | 10000001047 | 100000000943 | 1000000001261 |
| 10000813 | 100000841 | 1000000931 | 10000001051 | 100000000951 | 1000000001263 |
| 10000819 | 100000853 | 1000000933 | 10000001057 | 100000001009 | 1000000001293 |
| 10000831 | 100000891 | 1000000993 | 10000001087 | 100000001099 | 1000000001303 |
| 10000849 | 100000921 | 1000001011 | 10000001101 | 100000001111 | 1000000001339 |

## $[10^{13},10^{16}]$

| 1e13           | 1e14            | 1e15             | 1e16              |
| ---------------- | ----------------- | ------------------ | ------------------- |
| 10000000000037 | 100000000000031 | 1000000000000037 | 10000000000000061 |
| 10000000000051 | 100000000000067 | 1000000000000091 | 10000000000000069 |
| 10000000000099 | 100000000000097 | 1000000000000159 | 10000000000000079 |
| 10000000000129 | 100000000000099 | 1000000000000187 | 10000000000000099 |
| 10000000000183 | 100000000000133 | 1000000000000223 | 10000000000000453 |
| 10000000000259 | 100000000000139 | 1000000000000241 | 10000000000000481 |
| 10000000000267 | 100000000000169 | 1000000000000249 | 10000000000000597 |
| 10000000000273 | 100000000000183 | 1000000000000259 | 10000000000000613 |
| 10000000000279 | 100000000000261 | 1000000000000273 | 10000000000000639 |
| 10000000000283 | 100000000000357 | 1000000000000279 | 10000000000000669 |
| 10000000000313 | 100000000000367 | 1000000000000297 | 10000000000000753 |
| 10000000000343 | 100000000000403 | 1000000000000357 | 10000000000000793 |
| 10000000000391 | 100000000000423 | 1000000000000399 | 10000000000000819 |
| 10000000000411 | 100000000000469 | 1000000000000403 | 10000000000000861 |
| 10000000000433 | 100000000000487 | 1000000000000487 | 10000000000000897 |
| 10000000000453 | 100000000000493 | 1000000000000513 | 10000000000000909 |
| 10000000000591 | 100000000000541 | 1000000000000613 | 10000000000000931 |
| 10000000000609 | 100000000000601 | 1000000000000711 | 10000000000000949 |
| 10000000000643 | 100000000000643 | 1000000000000741 | 10000000000000957 |
| 10000000000649 | 100000000000657 | 1000000000000783 | 10000000000000991 |
| 10000000000657 | 100000000000709 | 1000000000000811 | 10000000000001029 |
| 10000000000687 | 100000000000721 | 1000000000000843 | 10000000000001101 |
| 10000000000691 | 100000000000753 | 1000000000000873 | 10000000000001129 |
| 10000000000717 | 100000000000777 | 1000000000000921 | 10000000000001239 |
| 10000000000729 | 100000000000807 | 1000000000001003 | 10000000000001293 |
| 10000000000751 | 100000000000841 | 1000000000001027 | 10000000000001311 |
| 10000000000759 | 100000000000843 | 1000000000001063 | 10000000000001321 |
| 10000000000777 | 100000000000861 | 1000000000001089 | 10000000000001377 |
| 10000000000853 | 100000000000963 | 1000000000001117 | 10000000000001423 |
| 10000000000883 | 100000000000993 | 1000000000001209 | 10000000000001477 |
| 10000000000943 | 100000000001087 | 1000000000001269 | 10000000000001549 |
| 10000000000957 | 100000000001089 | 1000000000001293 | 10000000000001551 |
| 10000000000987 | 100000000001129 | 1000000000001347 | 10000000000001567 |
| 10000000000993 | 100000000001173 | 1000000000001371 | 10000000000001657 |
| 10000000001011 | 100000000001177 | 1000000000001413 | 10000000000001659 |
| 10000000001023 | 100000000001189 | 1000000000001491 | 10000000000001719 |
| 10000000001087 | 100000000001197 | 1000000000001503 | 10000000000001723 |
| 10000000001093 | 100000000001203 | 1000000000001551 | 10000000000001731 |
| 10000000001141 | 100000000001273 | 1000000000001617 | 10000000000001743 |
| 10000000001161 | 100000000001303 | 1000000000001623 | 10000000000001747 |
| 10000000001177 | 100000000001381 | 1000000000001669 | 10000000000001771 |
| 10000000001191 | 100000000001387 | 1000000000001741 | 10000000000001789 |
| 10000000001207 | 100000000001413 | 1000000000001749 | 10000000000001833 |
| 10000000001239 | 100000000001423 | 1000000000001819 | 10000000000001873 |
| 10000000001261 | 100000000001467 | 1000000000001839 | 10000000000001939 |
| 10000000001267 | 100000000001549 | 1000000000001867 | 10000000000002013 |
| 10000000001269 | 100000000001593 | 1000000000001897 | 10000000000002049 |
| 10000000001291 | 100000000001611 | 1000000000002037 | 10000000000002053 |
| 10000000001309 | 100000000001623 | 1000000000002161 | 10000000000002083 |
| 10000000001339 | 100000000001647 | 1000000000002193 | 10000000000002137 |

## $[10^{17},10^{18}]$

| 1e17               | 1e18                |
| -------------------- | --------------------- |
| 100000000000000003 | 1000000000000000003 |
| 100000000000000013 | 1000000000000000009 |
| 100000000000000019 | 1000000000000000031 |
| 100000000000000021 | 1000000000000000079 |
| 100000000000000049 | 1000000000000000177 |
| 100000000000000081 | 1000000000000000183 |
| 100000000000000099 | 1000000000000000201 |
| 100000000000000141 | 1000000000000000283 |
| 100000000000000181 | 1000000000000000381 |
| 100000000000000337 | 1000000000000000387 |
| 100000000000000339 | 1000000000000000507 |
| 100000000000000369 | 1000000000000000523 |
| 100000000000000379 | 1000000000000000583 |
| 100000000000000423 | 1000000000000000603 |
| 100000000000000519 | 1000000000000000619 |
| 100000000000000543 | 1000000000000000621 |
| 100000000000000589 | 1000000000000000799 |
| 100000000000000591 | 1000000000000000841 |
| 100000000000000609 | 1000000000000000861 |
| 100000000000000669 | 1000000000000000877 |
| 100000000000000691 | 1000000000000000913 |
| 100000000000000781 | 1000000000000000931 |
| 100000000000000787 | 1000000000000000997 |
| 100000000000000817 | 1000000000000001093 |
| 100000000000000819 | 1000000000000001191 |
| 100000000000000871 | 1000000000000001267 |
| 100000000000000889 | 1000000000000001323 |
| 100000000000001053 | 1000000000000001347 |
| 100000000000001071 | 1000000000000001359 |
| 100000000000001093 | 1000000000000001453 |
| 100000000000001099 | 1000000000000001459 |
| 100000000000001107 | 1000000000000001537 |
| 100000000000001201 | 1000000000000001563 |
| 100000000000001219 | 1000000000000001593 |
| 100000000000001221 | 1000000000000001659 |
| 100000000000001243 | 1000000000000001683 |
| 100000000000001249 | 1000000000000001729 |
| 100000000000001287 | 1000000000000001743 |
| 100000000000001293 | 1000000000000001771 |
| 100000000000001327 | 1000000000000001827 |
| 100000000000001399 | 1000000000000001879 |
| 100000000000001429 | 1000000000000001953 |
| 100000000000001449 | 1000000000000002049 |
| 100000000000001459 | 1000000000000002097 |
| 100000000000001573 | 1000000000000002137 |
| 100000000000001603 | 1000000000000002217 |
| 100000000000001623 | 1000000000000002271 |
| 100000000000001641 | 1000000000000002319 |
| 100000000000001903 | 1000000000000002481 |
| 100000000000001921 | 1000000000000002493 |

## NTT 质数

$p=r2^k+1$

|p|r|k|g|
|----|----|----|----|
|3|1|1|2|
|5|1|2|2|
|17|1|4|3|
|97|3|5|5|
|193|3|6|5|
|257|1|8|3|
|7681|15|9|17|
|12289|3|12|11|
|40961|5|13|3|
|65537|1|16|3|
|786433|3|18|10|
|5767169|11|19|3|
|7340033|7|20|3|
|23068673|11|21|3|
|104857601|25|22|3|
|167772161|5|25|3|
|469762049|7|26|3|
|1004535809|479|21|3|
|2013265921|15|27|31|
|2281701377|17|27|3|
|3221225473|3|30|5|
|75161927681|35|31|3|
|77309411329|9|33|7|
|206158430209|3|36|22|
|2061584302081|15|37|7|
|2748779069441|5|39|3|
|6597069766657|3|41|5|
|39582418599937|9|42|5|
|79164837199873|9|43|5|
|263882790666241|15|44|7|
|1231453023109121|35|45|3|
|1337006139375617|19|46|3|
|3799912185593857|27|47|5|
|4222124650659841|15|48|19|
|7881299347898369|7|50|6|
|31525197391593473|7|52|3|
|180143985094819841|5|55|6|
|1945555039024054273|27|56|5|
|4179340454199820289|29|57|3|

最后修改：2024 年 07 月 17 日