所有九位素数中,各位数字的和能被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>
   
2. 
   
3. unsigned int a[31250000],t[99],d[10],i9,i8,i7,i6,i5,i4,i3,i2,i1,i,j,s;
   
4. 
   
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);