我希望拿到1至十億之間的素數

ejsoon · 发表于 2021-10-20 21:14:46

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

以「位數」作為分段，如：

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

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

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

二是威爾遜定理。（但是據我理解，這兩種方法好像是一種方法？）

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

（我猜測在某個素數網站，已經有人把這個做好了。）

白新岭 · 发表于 2021-10-20 23:40:16

十亿内素数表我有。你是要算法，还是要素数表？你的第一种方法，就是著名的筛法，也是划除法，把数排列成一排，然后逐步翻倍（加本数），划掉倍数，一直划到N，剔除后，剩下的即为素数。

TSC999 · 发表于 2021-10-21 09:29:37

Do[s[i] =
Print[10^i, "<p<", 10^(i + 1), " 区间共有 ",
PrimePi[10^(i + 1)] - PrimePi[10^i], " 个质数。"],
{i, 0, 10}];

复制代码

程序运行结果：

1<p<10 区间共有 4 个质数。
10<p<100 区间共有 21 个质数。
100<p<1000 区间共有 143 个质数。
1000<p<10000 区间共有 1061 个质数。
10000<p<100000 区间共有 8363 个质数。
100000<p<1000000 区间共有 68906 个质数。
1000000<p<10000000 区间共有 586081 个质数。
10000000<p<100000000 区间共有 5096876 个质数。
100000000<p<1000000000 区间共有 45086079 个质数。
1000000000<p<10000000000 区间共有 404204977 个质数。
10000000000<p<100000000000 区间共有 3663002302 个质数。

复制代码

TSC999 · 发表于 2021-10-21 12:01:32

我有不大于 2000 亿的质数表，但是没有办法上传。

ejsoon · 发表于 2021-10-22 05:59:22

TSC999 发表于 2021-10-21 12:01
我有不大于 2000 亿的质数表，但是没有办法上传。

可否從兩位數開始，分段給下？我想先拿到一萬的數。

ejsoon · 发表于 2021-10-22 09:04:15

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

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

附html+js代碼：

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>search prime number</title>
<style>
.txtaa {
width: 90%;
}
.cal_btn {
font-size: 24pt;
}
</style>
</head>
<body>
<button class="cal_btn" onclick="cal_prime()">GO!</button>
<h2 class="coltitle col1">1~9</h2>
<div class="col1 status">End, account are 4.</div>
<textarea class="txtaa tta1">2, 3, 5, 7</textarea>
<h2 class="coltitle col2">10~99</h2>
<div class="col2 status">waiting...</div>
<textarea class="txtaa tta2"></textarea>
<h2 class="coltitle col3">100~999</h2>
<div class="col3 status">waiting...</div>
<textarea class="txtaa tta3"></textarea>
<h2 class="coltitle col4">1000~9999</h2>
<div class="col4 status">waiting...</div>
<textarea class="txtaa tta4"></textarea>
<h2 class="coltitle col5">10000~99999</h2>
<div class="col5 status">waiting...</div>
<textarea class="txtaa tta5"></textarea>
<script>
function cal_prime () {
var prime_array = [2, 3, 5, 7]; // prime_number
var prime_point = 10; // prime_number point
var prime_count = 0; // prime_number aacount
while (prime_point < 99999) { // 10
for (var j = 0; j < prime_array.length && prime_point / 2 >= prime_array[j]; j++) { // 2, 3, [5], 7
if (Number.isInteger(prime_point / prime_array[j])) {
break;
}
}
if (j == prime_array.length || prime_point / 2 < prime_array[j]) {
prime_array.push(prime_point);
prime_count++;
if (prime_point < 99) {
document.querySelector(".tta2").value += prime_point + ', ';
} else if (prime_point < 999) {
document.querySelector(".tta3").value += prime_point + ', ';
} else if (prime_point < 9999) {
document.querySelector(".tta4").value += prime_point + ', ';
} else if (prime_point < 99999) {
document.querySelector(".tta5").value += prime_point + ', ';
}
}
prime_point++;
if (99 == prime_point) {
document.querySelector(".col2.status").innerHTML = "End, account are " + prime_count + ".";
prime_count = 0;
} else if (999 == prime_point) {
document.querySelector(".col3.status").innerHTML = "End, account are " + prime_count + ".";
prime_count = 0;
} else if (9999 == prime_point) {
document.querySelector(".col4.status").innerHTML = "End, account are " + prime_count + ".";
prime_count = 0;
} else if (99999 == prime_point) {
document.querySelector(".col5.status").innerHTML = "End, account are " + prime_count + ".";
prime_count = 0;
}
}
}
</script>
</body>
</html>

复制代码

ejsoon · 发表于 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秒鐘（視機器性能）。

ejsoon · 发表于 2021-10-22 09:21:31

prime.zip (22.4 KB, 下载次数: 2) （十萬以內的素數）

无心人 · 发表于 2021-11-12 08:29:40

除了30以内素数，后面素数都可以每30一个字节保存，10亿大概33M不压缩
甚至0-29.也可以保存2，3，5，三个数，再存成1字节

ejsoon · 发表于 2021-11-12 09:05:24

无心人发表于 2021-11-12 08:29
除了30以内素数，后面素数都可以每30一个字节保存，10亿大概33M不压缩
甚至0-29.也可以保存2，3，5，三个 ...

估計現在用量子計算機，能驗算出任何想要驗算的素數，就用這種最原始的辦法。

账号		自动登录	找回密码
密码			欢迎注册

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

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

問題已解決

点评

代碼已改進

点评