筛选一万亿内的素数
二七房屋出租-
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
筛选一万亿内任意一个区段的素数
函数参数：
as_1
decimal
value
筛选范围区段起点
as_2
decimal
value
筛选范围区段终点
as_return[]
decimal
reference
存放种子素数
as_return_value[]
decimal
reference
存放筛选结果
调用详解：
1.
必须定义的变量
dec
as_return[],as_return_value[]
_return,as_return_value
切勿赋值。
3.
筛选区段一般不大于
100
万为佳
，即
as_2
－
as_1<=1000
000,
函数允许区段超过
100
万。
4.
调用本函数
< br>f_prime_number(as_1,as_2,as_return,as_return_va lue)
_return_value
[]
就是生成的某区段内的素数
函数返回：
>=0
所找到素数的个数
<0
error
实际调用：求一万亿最后一个一万区段的素数
f_prime_number(99999999000
1.0,1.0,as_return,as_return_value)
要点及原理：
一
.
筛
100
万内素数：
1.
筛法原理，一个素数不能被它平方根以内的所有素数的倍数筛掉，它就是素数。
2.100
万的平方根是
1000
，所有只用
1000
< br>以内的素数就可以筛出
100
万内所有素数
3.
根据上面所说，程序分两步，
第一步
1000
以内进行筛选，第二部把
1000
以上的筛选
剩下的素数挑选出来
4.
第一步的具体思路：
a.
定义数组：
< br>p[1000001]
，数组下标表示数本身，初值为
0
，筛选时把素数的整数倍置为
-1
，<
/p>
29.
30.
31.
32.
33.
34.
35.
36.
37.
数
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
剩下为
0
的元素即为素数
b.2
是素数，其倍数是偶数，由
程序滤掉，不再筛
c.
筛选从种子的平方开始，因为其平方以内的的数以被前面的素数筛过了
d.
筛选的步长用种子的
2
倍，因为用种子作步长有一半是偶数，筛
过了
二
.
筛一万亿内的素数
1.
一万亿的内的素数不宜一下子
全筛出来，
可以一次以
100
万为单位
，
一个区段一个区段筛。
2.
算法要点如下：
a.
一万亿的平方根为
100
万，用
100
万以
内的素数可以筛出一万亿内的所有素数，所以函
首先自行计算一次
100
万以内的素数存入数组
as_return
。
b.
定义数组
p[1000001],
其下标与区段内的自然序号相对应，元素值
0
为素数，
1
不是
c.
根据
as_return
内的素数筛选至种子的平方大于筛选区间的上限
d.
计算出每个种子在指定区间内
筛掉的第一个数，然后按种子长度筛下去。
程序中语句为
“j=as_return
-
mod(k1,as_return)”
，如
i=12
，
as_return
< br>＝
37
则
j
＝
21
，
所以令
p[21]
＝
1
，即将
k1+21
筛掉（
k1
为区间起始值）再按步长
37
筛下去<
/p>
e.
偶数仍由程序筛掉，所以素数
2
不用
f.
数组
p
元素加上区间起始值
k1
就是实际要
求的素数
三
.
求更
大的素数，如求
1000
万平方
(10
0
万亿
)
内的素数
方法一，把本函数涉及到
100<
/p>
万的地方扩大
10
倍，即
ls_rang=10000000
，
p[10000
001],
这样
就可以求出
1000
万平方内的所有素数，但会有一定的时间和
资源开销，具体要看
实际硬件配置。
方法二，使用本函数计算出
1000
万
内的素数作为种子存放在数组或文件中，再使用
本函数的后半部分（内部函数
2
）筛选
1
万亿以上部分的素数。
方法二的实际调用示例：
//
求
1
万亿后第一个一万区段的素数
dec
as_return[],as_return_value[],temp[],k
56.
57.
58.
59.
60.
61.
62.
f_prime_number(1,10000000,
as_return,as_return_value)
as_return=as_return_value
as_return_value=temp
k=f_prime_number(1.0,1.0,as_return,as_return_value
)
四，函数的特殊调用：
为了提高效率（实际测试效果不明显），可以直接传入种子素数求大素数，如求
1
亿内最后
一个
63.
一百万的素数，实际用
1
万以内的素数作为种子就可以求出，而不用函数自行求出
100
万内
的素数
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
作为种子，以提高效率和节省资源。调用示例如下：
dec
as_return[],as_return_value[],temp[],k
f_prime_number(1,10000,as_return,as_ret
urn_value)
as_return=as_return_value
as_return_value=temp
k=f_prime_number(109000001.0,100000000.0,as_return
,as_return_value)
五
.
注
<
/p>
意，
修改或移植本函数是请务必考察目标系统规定的数据类型的精
度，
防治数据溢出。
六<
/p>
.
函数代码特点：
函数通过标志变量，把原本需三个函数完成的功能捆绑在了一个函数中，并通过变量的指
示
来完成递归。
===========================
====================================*/
//leeivan@
2003-07-05
dec
i,j,n,p[1000001],kk,k,t,ls_1,ls_2,temp[]
dec
k1,k2,k3,cl1[],cl2[],tmp
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
long
ls_rang,recursion_bz,tmp0
//
常量初始化
ls_rang=1000000
//
定义函数一次可计算的区段值，也是起始区段的上限
//
指示标志初始化，不可手工更改
，由程序自行设置
recursion_bz=0
//
递归标志
0
不递归，
1
递归；
//
变量初始化
as_1=abs(as_1)
as_2=abs(as_2)
if
as_2
then
ls_1=as_1
as_1=as_2
as_2=ls_1
end
if
ls_1=as_1
ls_2=as_2
if
ls_2>ls_rang
and
upperbound(as_return_value)=0
then
//
输入参数大于区段，或
跨起始区段，并
且函数第一次被调用时
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
//
强制函数自行计算一次起始区段以内的素数
ls_2=ls_rang
ls_1=0
//
设置函数递归标志，要求函数递归
recursion_bz=1
end
if
//
初始化
END
//=============
=
求
100
万以内的素数
===
内部函数
1
if
upperbound(as_return)=0
then
//
函数第一次执行时
二七房屋出租-