C语言求10亿内素数和

Python022

C语言求10亿内素数和,第1张

//没有编译环境所以用记事本写的。 整体程序可能会有一些细微的错误。你自己改一下。大致思路是这样。 //程序有效率需求。所以需要使用筛选法求大数素数 //注：程序在32位操作系统下运行int的取值范围是2的32次方=4294967296符合程序需求。如果是在 //dos的16位操作系统下int取值范围为65536。所以以下程序只能运行在32位或64位的操作系统下。 #include <stdlib.h>#include <stdio.h>#define NUM_LEN 50 //大数计算使用，结果可达到50位长度 int main() {char* CompositeNumFilterAndADD(int)int m,cchar* cc=CompositeNumFilterAndADD(1000000000)//返回的c是相加的结果 return 0} //求素数的程序 char* CompositeNumFilterAndADD(int n) { int i, j char* flag = (char*)malloc( n+1 )// 分配素数标记空间，flag[0]不使用所以需分配n+1个空间 int mpLen = 2*3*5*7*11*13// 采用memcpy以mpLen长的magicPattern来批量处理 char magicPattern[2*3*5*7*11*13]// 分配magicPattern空间 for (i=0i<mpLeni++) { magicPattern[i++] = 1 magicPattern[i++] = 0 magicPattern[i++] = 0 magicPattern[i++] = 0 magicPattern[i++] = 1 magicPattern[i] = 0 } for (i=4i<=mpLeni+=5) magicPattern[i] = 0 for (i=6i<=mpLeni+=7) magicPattern[i] = 0 for (i=10i<=mpLeni+=11) magicPattern[i] = 0 for (i=12i<=mpLeni+=13) magicPattern[i] = 0// 新的初始化方法,将2,3,5,7,11,13的倍数全干掉 // 而且采用memcpy以mpLen长的magicPattern来批量处理 int remainder = n%mpLen char* p = flag+1 char* pstop = p+n-remainder while (p <pstop) { memcpy(p, magicPattern, mpLen) p += mpLen } if (remainder >0) { memcpy(p, magicPattern, remainder) } flag[2] = 1 flag[3] = 1 flag[5] = 1 flag[7] = 1 flag[11] = 1 flag[13] = 1 // 从17开始filter，因为2,3,5,7,11,13的倍数早被kill了 // 到n/13止的 int stop = n/13 for (i=17i <= stopi++) { // i是合数，请歇着吧，因为您的工作早有您的质因子代劳了 if (0 == flag[i]) continue // 从i的17倍开始过滤 int step = i*2 for (j=i*17j <= nj+=step) { flag[j] = 0 } } // 统计素数和 char sum[NUM_LEN],num[NUM_LEN],Result[NUM_LEN]for (i=2i<=ni++) { if (flag[i]) { itoa(i, num, 10)//将int类型转换成字符串 int idx=add_str(sum,num,Result)sum=(char*)chResult+idx//大数相加相当于Result=sum+num； } } free(flag) return sum} //大数相加 int add_str(char * pch1,char * pch2 , char * chResult){ chResult[NUM_LEN-1]='\0'int idx=NUM_LEN-2 char *pEnd1=pch1,*pEnd2=pch2for(*pEnd1!='\0'pEnd1++)for(*pEnd2!='\0'pEnd2++)pEnd1--pEnd2--short flag=0//是否有进位 for((pEnd1!=pch1-1) || (pEnd2!=pch2-1)){ short b1=0if(pEnd1!=pch1-1){ b1= (short)(*pEnd1)-(short)'0'// '0' ->0 pEnd1--} short b2=0if(pEnd2!=pch2-1){ b2= (short)(*pEnd2)-(short)'0'// '0' ->0 pEnd2--} short sResult = b1+b2+flagflag=0if(sResult>9){flag=sResult/10sResult %=10} chResult[idx--] =(char)( sResult+(short)'0')} if(flag)chResult[idx--]=flag+(short)'0'return idx+1}

#include "stdio.h"void main()

{

int i,t,p

for(i=5i<=1000000000i++)

{

t=i

p=0

while(t)

{

p=p*10+t%10

t/=10

}

if(p==i)printf("%d ",i)

}

}