筛选一万亿内任意一个区段的素数
--------------------------------------------------------------------------------
第八军团 时间：2004-1-18 11:03:47
筛选一万亿内任意一个区段的素数
函数参数：as_1 decimal value 筛选范围区段起点
as_2 decimal value 筛选范围区段终点
as_return[] decimal reference 存放种子素数
as_return_value[] decimal reference 存放筛选结果
调用详解：1.必须定义的变量 dec as_return[],as_return_value[]
2.as_return,as_return_value切勿赋值。
3.筛选区段一般不大于100万为佳，即as_2－as_1 函数允许区段超过100万。
4.调用本函数f_prime_number(as_1,as_2,as_return,as_return_value)
5.as_return_value[]就是生成的某区段内的素数
函数返回：>=0 所找到素数的个数
实际调用：求一万亿最后一个一万区段的素数
f_prime_number(999999990001.0,1000000000000.0,as_return,as_return_value)
要点及原理：
一.筛100万内素数：
1.筛法原理，一个素数不能被它平方根以内的所有素数的倍数筛掉，它就是素数。
2.100万的平方根是1000，所有只用1000以内的素数就可以筛出100万内所有素数
3.根据上面所说，程序分两步，第一步1000以内进行筛选，第二部把1000以上的筛选
剩下的素数挑选出来
4.第一步的具体思路：
a.定义数组：p[1000001]，数组下标表示数本身，初值为0，筛选时把素数的整数倍置为-1，
剩下为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＝37
则j＝21，所以令p[21]＝1，即将k1+21筛掉（k1为区间起始值）再按步长37筛下去
e.偶数仍由程序筛掉，所以素数2不用
f.数组p元素加上区间起始值k1就是实际要求的素数
三.求更大的素数，如求1000万平方(100万亿)内的素数
方法一，把本函数涉及到100万的地方扩大10倍，即ls_rang=10000000，p[10000001],这样
就可以求出1000万平方内的所有素数，但会有一定的时间和资源开销，具体要看
实际硬件配置。
方法二，使用本函数计算出1000万内的素数作为种子存放在数组或文件中，再使用
本函数的后半部分（内部函数2）筛选1万亿以上部分的素数。
方法二的实际调用示例：
//求1万亿后第一个一万区段的素数
dec as_return[],as_return_value[],temp[],k
f_prime_number(1,10000000,as_return,as_return_value)
as_return=as_return_value
as_return_value=temp
k=f_prime_number(1000000000001.0,1000000010000.0,as_return,as_return_value)
四，函数的特殊调用：
为了提高效率（实际测试效果不明显），可以直接传入种子素数求大素数，如求1亿内最后一个
一百万的素数，实际用1万以内的素数作为种子就可以求出，而不用函数自行求出100万内的素数
作为种子，以提高效率和节省资源。调用示例如下：
dec as_return[],as_return_value[],temp[],k
f_prime_number(1,10000,as_return,as_return_value)
as_return=as_return_value
as_return_value=temp
k=f_prime_number(109000001.0,100000000.0,as_return,as_return_value)
五.注 意，修改或移植本函数是请务必考察目标系统规定的数据类型的精度，防治数据溢出。
六.函数代码特点：
函数通过标志变量，把原本需三个函数完成的功能捆绑在了一个函数中，并通过变量的指示
来完成递归。
===============================================================*/
//leeivan@163.com 2003-07-05
dec i,j,n,p[1000001],kk,k,t,ls_1,ls_2,temp[]
dec k1,k2,k3,cl1[],cl2[],tmp
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 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 //输入参数大于区段，或跨起始区段，并且函数第一次被调用时
//强制函数自行计算一次起始区段以内的素数
ls_2=ls_rang
ls_1=0
//设置函数递归标志，要求函数递归
recursion_bz=1
end if
//初始化END
//==============求100万以内的素数=== 内部函数 1
if upperbound(as_return)=0 then //函数第一次执行时
kk=ls_2
k=truncate(sqrt(kk),0)
if ls_1 n=1
as_return[1]=2
end if
for i=3 to k step 2
if p=0 then
if i>=ls_1 then
n++
as_return[n]=i
end if
j=i*i
do while j p[j]=-1
j+=2*i
loop
end if
next
k++
if mod(k,2)=0 then k++
for i=k to kk step 2
if p=0 then
if i>=ls_1 then
n++
as_return[n]=i
end if
end if
next
//所求素数属于起始区段范围内，直接返回
if recursion_bz1 then
as_return_value=as_return
as_return=temp
return upperbound(as_return_value)
end if
end if
//====100万以内素数计算完毕==== 内部函数 1 END
//主函数，控制整个函数流程
if recursion_bz=1 then //所求素数不属于或跨起始区段,要求递归时
//按照区段值拆分输入的参数
tmp=(as_2 -as_1+1)/ls_rang
if Truncate (tmp, 0 )tmp then tmp=Truncate (tmp,0)+1
for tmp0=1 to tmp
cl1[tmp0]=(tmp0 -1)*ls_rang+as_1
cl2[tmp0]=cl1[tmp0]+ls_rang -1
if cl2[tmp0]>as_2 then cl2[tmp0]=as_2
next
//进行递归
for tmp0=1 to tmp
if upperbound( as_return_value)=0 then as_return_value[1]=0
f_prime_number(cl1[tmp0],cl2[tmp0],as_return,as_return_value)
next
//整个函数返回
as_return=temp
return upperbound(as_return_value)
end if
//初始化，为求100万以上某区段内的素数准备
if as_return_value[1]=0 then as_return_value=temp
k1=as_1
if mod(as_1,2)0 then k1 --
k2=as_2
k3=k2 -k1
//初始化END
//修正跨某个特殊区段引起的数据遗漏
//特殊区段：起始区段上限的平方根以内到起始区段上限以外所组成的一个区段
n=upperbound(as_return_value)+1
if k1 for tmp0=1 to 168 //起始区段上限的平方根以内的素数个数
if as_return[tmp0]>=k1 then
as_return_value[n]=as_return[tmp0]
n++
end if
next
end if
//修正END
//==================求100万以上某区段内的素数 内部函数 2
//本函数由主函数调用
n=upperbound(as_return_value)+1
t=upperbound(as_return)
debugbreak()
for i= 1 to t
if as_return * as_return>k2 then exit
j=as_return -mod(k1,as_return)
do while j p[j]=1
j=j+as_return
loop
next
if k1 for i=1 to k3 step 2
if p as_return_value[n]=i+k1
n++
end if
next
return 0
