所有九位素数中,各位数字的和能被2-9整除的各有多少个
所有九位素数中,各位数字的和能被2-9整除的各有多少个?比如: 490450003各位数字的和能被5整除 为什么把3、6、9也考虑进来？
怎么可能被3、6、9整除？
不是只有2、4、5、7、8值得讨论吗？ 本帖最后由 wayne 于 2010-1-16 11:26 编辑
对，可以拿来讨论的只有
2，4，5，7，8 本帖最后由 wayne 于 2010-1-16 11:31 编辑
我想，题是这么问的
但宜分别讨论，
不同的数会有不同的快速算法
比如2，只需遍历所有素数，判断素数有偶数个奇数数字就是了 呵呵,疏忽了.有朋友问,就直接贴上来了,就以5和8为例,有什么快速的计算方法.最初打算下载一个素数表的,查一下,九位素数个数为45086079个,放弃了 穷举法 4# wayne
判断素数有偶数个奇数数字,
判断奇数的个数也应该需要遍历每一位吧？这样速度也应该不会太快吧。 现在只要个得数,我算了2小时也没算出来,谁给个答案?只要5 和8 的就行了 本帖最后由 KeyTo9_Fans 于 2010-1-17 13:57 编辑
代码如下：#include<cstdio>
unsigned int a,t,d,i9,i8,i7,i6,i5,i4,i3,i2,i1,i,j,s;
int main()
{
for(i=2;i<31622;i++)
if(!(a&(1<<(i&31)))) //a数组是把32个bit压成一个int
for(j=i*i;j<1000000000;j+=i)a|=1<<(j&31); //在a数组中做筛法
printf("-----------\n");
s=1; //s变量表示每一位数字的和
i=100000000; //i变量表示当前的9位数
for(i9=1;i9<10;i9++,s++) //9重循环枚举每一位数，实时更新s变量
for(s-=i8,i8=0;i8<10;i8++,s++)
for(s-=i7,i7=0;i7<10;i7++,s++)
for(s-=i6,i6=0;i6<10;i6++,s++)
for(s-=i5,i5=0;i5<10;i5++,s++)
for(s-=i4,i4=0;i4<10;i4++,s++)
for(s-=i3,i3=0;i3<10;i3++,s++)
for(s-=i2,i2=0;i2<10;i2++,s++)
for(s-=i1,i1=0;i1<10;i1++,s++)
{
if(!(a&(1<<(i&31))))t++; //把数字和为s的素数统计到t数组中
i++;
}
for(i=0;i<99;i++)
for(j=1;j<10;j++)
if(i%j==0)d+=t; //把数字的和能被1到9整除的素数统计到d数组中
for(i=1;i<10;i++)
printf("%d: %d\n",i,d);
printf("-----------\n");
return 0;
}优点：
实时更新数字和，不用每次都把9位数字累加一遍:)
缺点：
筛法比较慢，不如mathe写的筛法代码跑得快:(
运行时间：
筛法：60秒
枚举每一位数字并统计结果：6秒
处理统计数据并输出：忽略
总计：66秒
输出结果如下：-----------
1: 45086079
2: 22543062
3: 0
4: 11275826
5: 9019962
6: 0
7: 6280065
8: 5694094
9: 0
-----------##########
优化方案：
枚举9位数从100000001开始，每次加2，比每次加1快2倍，使得：
筛法：60秒
枚举数字：3秒
总计：63秒
但枚举数字不是算法的瓶颈，改进筛法更重要。 多谢了!
先筛出31622以下的素数P[]
再用P[]筛10亿以内的素数
for(j=P*P;j<1000000000;j+=2*P)a|=1<<(j&31);
页:
[1]
2