用C语言求素数的优化用C语言求素数的优化
这个程序运行了8个小时,求一亿以内的素数和超级素数.
大家帮忙看看,我求一亿以内的素数和超级素数.从下午5:30开始,一直到零晨0点30才结束.我的电脑配置也可以.INTER E7500的CPU,G41的板子,前端总线1333,2G 1333的内存.大家看看这个程序还可以怎提高一下效率!
c++
1.
程序代码:
#include
#include
long int prime(long int i) /*求素数的涵数*/
{
int x;
for(x=2;xsqrt...
用C语言求素数的优化
这个程序运行了8个小时,求一亿以内的素数和超级素数.
大家帮忙看看,我求一亿以内的素数和超级素数.从下午5:30开始,一直到零晨0点30才结束.我的电脑配置也可以.INTER E7500的CPU,G41的板子,前端总线1333,2G 1333的内存.大家看看这个程序还可以怎提高一下效率!
c++
1.
程序代码:
#include
#include
long int prime(long int i) /*求素数的涵数*/
{
int x;
for(x=2;x<=sqrt(i);x++)
if(i%x==0)return 1; /*不是素数返回主调涵数1*/
if(x>sqrt(i))return 0; /*是素数返回主调涵数0*/ }
long int answer()/*此涵数调用prime()得到结果,并输出*/ {
long int x;
printf("\ninput a numbers:\n");
scanf("\t%ld",&x);
if(prime(x)) /*从被调涵数得到结果判断真假并输出相应结果*/
printf("No\t");
else
printf("yes\t");
}
long int prime_super(long int x) /*此涵数判断是否为超级涵数*/ {
int a,c,b;
a=prime(x); /*调用判断素数的子涵数,得到被调涵数返回的0或者1*/
b=0;
if(x>19)
{
while(a==0&&b==0&&x>9)/*当第一次判断返回为0时,再循环直到被调涵数返回值为1或X小于是2位数。*/
{
x=x/10; /*将X去掉最后一位。*/
if(x>1)b+=prime(x); /*如果每次返回都是0,最高位不是1,那么B就一直是0*/
else b++;
}
if(b==0&&a==0) /*所有返回值都为0时,这个数是超级素数,返回主调涵数0*/
return 0;
}
else return 1;
}
long int in_n(long int a) /*此涵数求N以内的所有超级素数或求N是否为素数*/
{
long int i=2,x,c,d=0,e=0,y;
printf("input a number:\n");
input: scanf("%ld",&x);
if(x<=2) /*如果输入的数小于11时返回重输入*/
{
printf("the numbers to small,please input a number:\n");
goto input;
}
if(a==51||a==52||a==53) /*当主调涵数传来的值为‘3’或‘4’或'5'时,要求求N以内的所有超级素数或素数或两个一起求*/
{
while(i<=x) /*i从3开始,一直到输入的X大为止。*/
{
if(a==51)c=prime_super(i);/*如果主调涵数传来的值为‘3’,要求求N以内的所有超级素数*/
else c=prime(i); /*如果主调涵数传来的值不为‘3’,要求求N以内的所有素数*/
if(!c) /*返回为1时做以下程序*/
{
if(a==53) /*如果主调涵数传来的值为'5',要求求N以内所有素数与超级素数.*/
{
if(!(c=prime_super(i)))/*就在求素数的同时调用prime_super(i)涵数求超级涵数*/
{
printf("\b\b>>");d++; /*用>标级所有素数中的超级素数,并记录个数*/
}
}
printf("%ld \t",i); /*打印出是素的数*/
e++; /*记录多少个数*/
}
i++;
}
if(a==53)
printf("\n\tin %ld within super prime numbers sum is %ld ",x,d);
/*打印出超级素数的个数*/
printf("\n\tin %ld within prime numbers sum is %ld ",x,e);
/*打印出素数的个数*/
printf("\nIf necessary validate,press any key.exit press\"q\"\n");/*提示
是否需要手动输入验证得到的任何一个素数的正确性。*/
getchar(); /*当输入为“Q”时,结束程序;否则继续*/
while(getchar()!='q')
answer(); /*调用子涵数手动输入,去掉最后位验证*/
}
if(a==50) /*当主调涵数传来的值为‘2’时,要求求1个数
是否为超级素数*/
{
if(!(c=prime_super(x)))
printf("\n%ld is super prime Number\n",x);
else printf("\n%ld no super primeNumber\n",x);
}
}
main()
{
int i;
printf("\nanswer any a numbers whether prime Number,press \"1\";\nanswer any a
numbers whether super prime Number,press \"2\";\nanswer in \"n\" within all super
prime Number,press \"3\";");
printf("\nanswer in \"n\" within all prime Number,press \"4\";\nanswer in \"n\"
within all prime Number and super prime Number,press \"5\".\n");
i=getchar();
switch(i)
{
case '1': answer(); break; /*按1,求任何一个数是否素数*/
case '2': in_n(i); break; /*按2,求任何一个数是否超级素数*/
case '3': in_n(i); break; /*按3,求任何一个数以内的所有超级素数*/
case '4': in_n(i); break; /*按4,求任何一个数以内的所有素数*/
case '5': in_n(i); break; /*按5,求任何一个数以内的所有素数及超级
素数*/
default: break;
}
}
2.
/*-----------------------*
用筛法产生1亿以内的素数表
(VC++6.0及128MB以上内存)
*-----------------------*/ #include
#include
#define NMAX 100000000 #define SQRN 10000
main()
{
static char a[NMAX];//static不能省略
unsigned long k,i,total=0;//统计素数
for(k=2;k<=SQRN;k++)if(!a[k])
for(i=2*k;i
本文档为【用C语言求素数的优化】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。