一万亿内的素数.txt

上次站长没用!今次打包几个ACM的资料在上传

筛选一万亿内任意一个区段的素数 

函数参数：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<=1000000, 
          函数允许区段超过100万。 
        4.调用本函数f_prime_number(as_1,as_2,as_return,as_return_value) 
        5.as_return_value[]就是生成的某区段内的素数 
函数返回：>=0 所找到素数的个数 
          <0 error 

实际调用：求一万亿最后一个一万区段的素数 
        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) 

  五.注  意，修改或移植本函数是请务必考察目标系统规定的数据类型的精度，防治数据溢出。    

  六.函数代码特点： 
      函数通过标志变量，把原本需三个函数完成的功能捆绑在了一个函数中，并通过变量的指示 
      来完成递归。 

===============================================================*/ 
//[e-mail]  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<as_1 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 //输入参数大于区段，或跨起始区段，并且函数第一次被调用时 
  //强制函数自行计算一次起始区段以内的素数 
  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<3 then 
    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<=kk 
          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_bz<>1  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<truncate(sqrt(ls_rang),0) then 
  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<=k3 
    p[j]=1 
    j=j+as_return 
  loop 
next 
if k1<2 then p[1]=1 
for i=1 to k3 step 2 
  if p<1  then 
      as_return_value[n]=i+k1 
      n++ 
  end if 
next 

return 0