所有九位素数中,各位数字的和能被2-9整除的各有多少个

northwolves

所有九位素数中,各位数字的和能被2-9整除的各有多少个? 比如: 490450003各位数字的和能被5整除

KeyTo9_Fans

为什么把3、6、9也考虑进来？ 怎么可能被3、6、9整除？ 不是只有2、4、5、7、8值得讨论吗？

wayne

对，可以拿来讨论的只有 2，4，5，7，8

wayne

我想，题是这么问的 但宜分别讨论， 不同的数会有不同的快速算法 比如2，只需遍历所有素数，判断素数有偶数个奇数数字就是了

northwolves

呵呵,疏忽了.有朋友问,就直接贴上来了,就以5和8为例,有什么快速的计算方法.最初打算下载一个素数表的,查一下,九位素数个数为45086079个,放弃了

〇〇

穷举法

winxos

4# wayne 判断素数有偶数个奇数数字, 判断奇数的个数也应该需要遍历每一位吧？这样速度也应该不会太快吧。

northwolves

现在只要个得数,我算了2小时也没算出来,谁给个答案?只要5 和8 的就行了

KeyTo9_Fans

代码如下：

1. #include<cstdio>
3. unsigned int a[31250000],t[99],d[10],i9,i8,i7,i6,i5,i4,i3,i2,i1,i,j,s;
5. int main()
6. {
7. for(i=2;i<31622;i++)
8. if(!(a[i>>5]&(1<<(i&31)))) //a数组是把32个bit压成一个int
9. for(j=i*i;j<1000000000;j+=i)a[j>>5]|=1<<(j&31); //在a数组中做筛法
10. printf("-----------\n");
11. s=1; //s变量表示每一位数字的和
12. i=100000000; //i变量表示当前的9位数
13. for(i9=1;i9<10;i9++,s++) //9重循环枚举每一位数，实时更新s变量
14. for(s-=i8,i8=0;i8<10;i8++,s++)
15. for(s-=i7,i7=0;i7<10;i7++,s++)
16. for(s-=i6,i6=0;i6<10;i6++,s++)
17. for(s-=i5,i5=0;i5<10;i5++,s++)
18. for(s-=i4,i4=0;i4<10;i4++,s++)
19. for(s-=i3,i3=0;i3<10;i3++,s++)
20. for(s-=i2,i2=0;i2<10;i2++,s++)
21. for(s-=i1,i1=0;i1<10;i1++,s++)
22. {
23. if(!(a[i>>5]&(1<<(i&31))))t[s]++; //把数字和为s的素数统计到t数组中
24. i++;
25. }
26. for(i=0;i<99;i++)
27. for(j=1;j<10;j++)
28. if(i%j==0)d[j]+=t[i]; //把数字的和能被1到9整除的素数统计到d数组中
29. for(i=1;i<10;i++)
30. printf("%d: %d\n",i,d[i]);
31. printf("-----------\n");
32. return 0;
33. }

复制代码

优点： 实时更新数字和，不用每次都把9位数字累加一遍 缺点： 筛法比较慢，不如mathe写的筛法代码跑得快 运行时间： 筛法：60秒 枚举每一位数字并统计结果：6秒 处理统计数据并输出：忽略 总计：66秒 输出结果如下：

1. -----------
2. 1: 45086079
3. 2: 22543062
4. 3: 0
5. 4: 11275826
6. 5: 9019962
7. 6: 0
8. 7: 6280065
9. 8: 5694094
10. 9: 0
11. -----------

复制代码

########## 优化方案： 枚举9位数从100000001开始，每次加2，比每次加1快2倍，使得： 筛法：60秒 枚举数字：3秒 总计：63秒 但枚举数字不是算法的瓶颈，改进筛法更重要。

northwolves

多谢了! 先筛出31622以下的素数P[] 再用P[]筛10亿以内的素数 for(j=P[i]*P[i];j<1000000000;j+=2*P[i])a[j>>5]|=1<<(j&31);