数学研发论坛

 找回密码
 欢迎注册
查看: 248|回复: 13

[提问] 我希望拿到1至十億之間的素數

[复制链接]
发表于 2021-10-20 21:14:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
以「位數」作為分段,如:

一位數:2,3,5,7
二位數:11,13,17,19...
三位數:…
四位數:…



至十億是十位數。順帶統計一下每一段有幾個素數。




就寡人知道的方法有兩個,一個是逐篩法(不知叫甚麼名字),就是拿前面已知的素數去倍乘,篩出後来的素數。

二是威爾遜定理。(但是據我理解,這兩種方法好像是一種方法?)

因為近日在構思一個用素數来做的遊戲,所以需要這個。請本壇各路高手幫下忙,感謝!

(我猜測在某個素數網站,已經有人把這個做好了。)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-11-12 08:29:40 | 显示全部楼层
除了30以内素数,后面素数都可以每30一个字节保存,10亿大概33M不压缩
甚至0-29.也可以保存2,3,5,三个数,再存成1字节
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-20 23:40:16 | 显示全部楼层
十亿内素数表我有。你是要算法,还是要素数表?你的第一种方法,就是著名的筛法,也是划除法,把数排列成一排,然后逐步翻倍(加本数),划掉倍数,一直划到N,剔除后,剩下的即为素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-21 09:29:37 | 显示全部楼层
  1. Do[s[i] =
  2.    Print[10^i, "<p<", 10^(i + 1), " 区间共有 ",
  3.     PrimePi[10^(i + 1)] - PrimePi[10^i], " 个质数。"],
  4.   {i, 0, 10}];
复制代码


程序运行结果:

  1. 1<p<10 区间共有 4 个质数。
  2. 10<p<100 区间共有 21 个质数。
  3. 100<p<1000 区间共有 143 个质数。
  4. 1000<p<10000 区间共有 1061 个质数。
  5. 10000<p<100000 区间共有 8363 个质数。
  6. 100000<p<1000000 区间共有 68906 个质数。
  7. 1000000<p<10000000 区间共有 586081 个质数。
  8. 10000000<p<100000000 区间共有 5096876 个质数。
  9. 100000000<p<1000000000 区间共有 45086079 个质数。
  10. 1000000000<p<10000000000 区间共有 404204977 个质数。
  11. 10000000000<p<100000000000 区间共有 3663002302 个质数。
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-21 12:01:32 | 显示全部楼层
我有不大于 2000 亿的质数表,但是没有办法上传。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-22 05:59:22 | 显示全部楼层
TSC999 发表于 2021-10-21 12:01
我有不大于 2000 亿的质数表,但是没有办法上传。

可否從兩位數開始,分段給下?我想先拿到一萬的數。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-22 09:04:15 | 显示全部楼层

問題已解決

本帖最后由 ejsoon 于 2021-10-22 15:56 编辑

寡人自己寫了個html+js,拿到了十萬以內的素數。感謝各位,寡人覺的應該已經夠用了。

附html+js代碼:

  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4.         <meta charset="UTF-8">
  5.         <title>search prime number</title>
  6.         <style>
  7. .txtaa {
  8.         width: 90%;
  9. }
  10. .cal_btn {
  11.         font-size: 24pt;
  12. }
  13.         </style>
  14. </head>
  15. <body>
  16.         <button class="cal_btn" onclick="cal_prime()">GO!</button>
  17.         <h2 class="coltitle col1">1~9</h2>
  18.         <div class="col1 status">End, account are 4.</div>
  19.         <textarea class="txtaa tta1">2, 3, 5, 7</textarea>
  20.         <h2 class="coltitle col2">10~99</h2>
  21.         <div class="col2 status">waiting...</div>
  22.         <textarea class="txtaa tta2"></textarea>
  23.         <h2 class="coltitle col3">100~999</h2>
  24.         <div class="col3 status">waiting...</div>
  25.         <textarea class="txtaa tta3"></textarea>
  26.         <h2 class="coltitle col4">1000~9999</h2>
  27.         <div class="col4 status">waiting...</div>
  28.         <textarea class="txtaa tta4"></textarea>
  29.         <h2 class="coltitle col5">10000~99999</h2>
  30.         <div class="col5 status">waiting...</div>
  31.         <textarea class="txtaa tta5"></textarea>
  32.         <script>
  33.                 function cal_prime () {
  34.                         var prime_array = [2, 3, 5, 7]; // prime_number
  35.                         var prime_point = 10; // prime_number point
  36.                         var prime_count = 0; // prime_number aacount
  37.                         while (prime_point < 99999) { // 10
  38.                                 for (var j = 0; j < prime_array.length && prime_point / 2 >= prime_array[j]; j++) { // 2, 3, [5], 7
  39.                                         if (Number.isInteger(prime_point / prime_array[j])) {
  40.                                                 break;
  41.                                         }
  42.                                 }
  43.                                 if (j == prime_array.length || prime_point / 2 < prime_array[j]) {
  44.                                         prime_array.push(prime_point);
  45.                                         prime_count++;
  46.                                         if (prime_point < 99) {
  47.                                                 document.querySelector(".tta2").value += prime_point + ', ';
  48.                                         } else if (prime_point < 999) {
  49.                                                 document.querySelector(".tta3").value += prime_point + ', ';
  50.                                         } else if (prime_point < 9999) {
  51.                                                 document.querySelector(".tta4").value += prime_point + ', ';
  52.                                         } else if (prime_point < 99999) {
  53.                                                 document.querySelector(".tta5").value += prime_point + ', ';
  54.                                         }
  55.                                 }
  56.                                 prime_point++;
  57.                                 if (99 == prime_point) {
  58.                                         document.querySelector(".col2.status").innerHTML = "End, account are " + prime_count + ".";
  59.                                         prime_count = 0;
  60.                                 } else if (999 == prime_point) {
  61.                                         document.querySelector(".col3.status").innerHTML = "End, account are " + prime_count + ".";
  62.                                         prime_count = 0;
  63.                                 } else if (9999 == prime_point) {
  64.                                         document.querySelector(".col4.status").innerHTML = "End, account are " + prime_count + ".";
  65.                                         prime_count = 0;
  66.                                 } else if (99999 == prime_point) {
  67.                                         document.querySelector(".col5.status").innerHTML = "End, account are " + prime_count + ".";
  68.                                         prime_count = 0;
  69.                                 }
  70.                         }
  71.                 }
  72.         </script>
  73. </body>
  74. </html>
复制代码

点评

如果能有系統的訓練,能提升數學水平,那就最好了。現在我很多話題都看不懂,怪自己當初沒有選擇數學專業。  发表于 2021-10-22 12:35
总算有存在感,自己有了解决的办法就好,公布出来,让大家分享更好。  发表于 2021-10-22 11:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-22 09:18:11 | 显示全部楼层

代碼已改進

本帖最后由 ejsoon 于 2021-10-22 15:58 编辑

Firefox_Screenshot_2021-10-22T01-05-08.868Z.png

此乃截圖。

算到99999是要等個半分鐘左右,

可以把32行的五個9改成四個9,                while (prime_point < 99999) {

則會快很多。

這就是js的效率了,因為寡人要求也不高。如果很吃硬件的話,還是需要用到python,c等語言。


後来發現是寡人寫的代碼不對,因此才拖累了效率,現在代碼已更新,只要1~3秒鐘(視機器性能)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-10-22 09:21:31 | 显示全部楼层
prime.zip (22.4 KB, 下载次数: 0)

点评

我後面發現我應該只用到十萬以內就足夠了。十億有點太嚇人。不過如果真的要分享一個95M的文檔,也不是沒有辦法。  发表于 2021-10-25 14:11
我把 10 亿以内的素数表经压缩成 zip 文件后仍有 95M,此网站只能上传 0.5M 的文件,相差太悬殊了。  发表于 2021-10-25 14:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-11-12 09:05:24 | 显示全部楼层
无心人 发表于 2021-11-12 08:29
除了30以内素数,后面素数都可以每30一个字节保存,10亿大概33M不压缩
甚至0-29.也可以保存2,3,5,三个 ...

估計現在用量子計算機,能驗算出任何想要驗算的素數,就用這種最原始的辦法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-11-29 10:21 , Processed in 0.062342 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表