列举100万以内的素数
作者: ameya执行次数: 13362
※ 本程序库由会员创建。本站不对其内容负责。
可通过埃拉托斯特尼筛法显示100万以内的素数。
我使用了所谓的“轮筛法”这种加速技术。大概吧。
虽然没太看懂英文的讲解,但我根据维基百科上的图片推测,试着随意组装了一下。
/* 首先,从2*3*5*7=210以内的自然数中剔除2、3、5、7的倍数,准备一个名为Wheel的数组。由于处理需要,数组范围扩展到了211,但这只是“210+1”,而它恰好是下一个质数。 */
numeric wheel[] = {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,211};
/* Wheel的元素个数为 */
whlen = 48;
/* 准备一个包含差分(的1/2)的数组(由于某些原因,起始位置偏移了1。因为旋转处理比较麻烦,所以准备了两轮的数据)*/
numeric ntb105[] = {1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5};
/* 还创建了一个用于从筛的索引中减去Wheel上位置的数组 */
numeric nrev105[105];
for (k = 1; k <= whlen; k = k + 1) {
nrev105[(wheel[k] - 3) / 2] = k - 1;
}
/* 剩下的就是随意转一转之类的 */
numeric numx[48];
idx = 4;
while (idx < enphsiev) {
for (z = 0; z < whlen; z = z + 1) {
if (sieve[idx] == 0) {
m = nrev105[mod(idx, 105)]; /* wheel起始位置 */
num = idx * 2 + 3; /* 该表达式将sieve的索引转换为实际数值 */
j = ((num * num) - 3) / 2; /* 这是将平方值逆向转换回索引 */
for (k = 0; k < whlen; k = k + 1) {
numx[k] = ntb105[m + k] * num; /* 由于乘法运算开销较大,因此预先计算并存入查找表 */
}
while (j < sievemax) { /* 筛法的主循环 */
for (k = 0; k < whlen; k = k + 1) {
sieve[j] = 1;
j = j + numx[k];
}
}
}
idx = idx + ntb105[z];
if (idx >= enphsiev) {break;}
}
}
※筛法数组 sieve[idx] 的对应关系如下:idx=0 → 3,idx=1 → 5,idx=2 → 7。
※顺便提一下,在主循环中,sieve[j] 的参数 j 最多会超过 maxsieve 值 whlen-1,因此需要采取相应的措施。
※要完成该程序,还需要以下内容以及显示结果的处理。
/* 假设输入变量为 UpperLimit */
sievemax = ceiling(UpperLimit / 2);
enphsiev = int(sqrt(UpperLimit) / 2);
/* 输入数值在修改前似乎被视为常量,因此可用于数组参数 */
numeric sieve[UpperLimit];
虽然没太看懂英文的讲解,但我根据维基百科上的图片推测,试着随意组装了一下。
/* 首先,从2*3*5*7=210以内的自然数中剔除2、3、5、7的倍数,准备一个名为Wheel的数组。由于处理需要,数组范围扩展到了211,但这只是“210+1”,而它恰好是下一个质数。 */
numeric wheel[] = {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,211};
/* Wheel的元素个数为 */
whlen = 48;
/* 准备一个包含差分(的1/2)的数组(由于某些原因,起始位置偏移了1。因为旋转处理比较麻烦,所以准备了两轮的数据)*/
numeric ntb105[] = {1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5};
/* 还创建了一个用于从筛的索引中减去Wheel上位置的数组 */
numeric nrev105[105];
for (k = 1; k <= whlen; k = k + 1) {
nrev105[(wheel[k] - 3) / 2] = k - 1;
}
/* 剩下的就是随意转一转之类的 */
numeric numx[48];
idx = 4;
while (idx < enphsiev) {
for (z = 0; z < whlen; z = z + 1) {
if (sieve[idx] == 0) {
m = nrev105[mod(idx, 105)]; /* wheel起始位置 */
num = idx * 2 + 3; /* 该表达式将sieve的索引转换为实际数值 */
j = ((num * num) - 3) / 2; /* 这是将平方值逆向转换回索引 */
for (k = 0; k < whlen; k = k + 1) {
numx[k] = ntb105[m + k] * num; /* 由于乘法运算开销较大,因此预先计算并存入查找表 */
}
while (j < sievemax) { /* 筛法的主循环 */
for (k = 0; k < whlen; k = k + 1) {
sieve[j] = 1;
j = j + numx[k];
}
}
}
idx = idx + ntb105[z];
if (idx >= enphsiev) {break;}
}
}
※筛法数组 sieve[idx] 的对应关系如下:idx=0 → 3,idx=1 → 5,idx=2 → 7。
※顺便提一下,在主循环中,sieve[j] 的参数 j 最多会超过 maxsieve 值 whlen-1,因此需要采取相应的措施。
※要完成该程序,还需要以下内容以及显示结果的处理。
/* 假设输入变量为 UpperLimit */
sievemax = ceiling(UpperLimit / 2);
enphsiev = int(sqrt(UpperLimit) / 2);
/* 输入数值在修改前似乎被视为常量,因此可用于数组参数 */
numeric sieve[UpperLimit];
- 相关链接
目前还没有关于此计算的用户评价。