洋葱素数

无心人

假设一个素数去掉十进制最高位一个数字还是素数，称外洋葱素数 假设一个素数去掉十进制最低位一个数字还是素数，称内洋葱素数 现在求小于等于10^19的全部这类数字 ================================================= 高中用计算器算过，挺好玩的一个东西

无心人

内洋葱素数很好处理 除最高位外数字都是1, 3, 7, 9，最高位是3, 5, 7, 9 外洋葱素数组合多的多，但最低位必须是3, 7, 9

gxqcn

惨了，这个版块快成了素数专辑了！

无心人

等我再出一个容易的问题

mathe

外洋葱: 3484957213536676883 6484957213536676883 8963315421273233617 7986315421273233617 6312646216567629137 4686798799354632647 6918997653319693967 8918997653319693967 3396334245663786197 5396334245663786197 1276812967623946997 6276812967623946997 6165678739293946997 Total 13 for length 19 36484957213536676883 67986315421273233617 86312646216567629137 18918997653319693967 15396334245663786197 66276812967623946997 Total 6 for length 20 367986315421273233617 686312646216567629137 918918997653319693967 315396334245663786197 666276812967623946997 Total 5 for length 21 6686312646216567629137 7686312646216567629137 5918918997653319693967 9918918997653319693967 Total 4 for length 22 96686312646216567629137 57686312646216567629137 95918918997653319693967 Total 3 for length 23 357686312646216567629137 Total 1 for length 24 Total 0 for length 25 Total 4259 found

medie2005

mathe说一下算法吧.

mathe

这个基本上算不上什么算法，简单从短的向长的构造就可以了。 先是1位的只有3，5，7，然后每次前面添加一位看看是否还是素数（用HugeCalc判断就可以了）

1. #include <list>
2. using namespace std;
3. ....
4. typedef CHugeInt integer;
5. typedef list<integer> THE_LIST;
6. THE_LIST list1,list2;
7. THE_LIST *orig_list, *new_list, *tmp_list;
8. #define MAX_N 50
10. int i,j;
11. integer v(1);
12. int count=3;
13. list1.push_back(integer(3));list1.push_back(integer(5));list1.push_back(integer(7));
14. orig_list=&list1;
15. new_list=&list2;
16. printf("3\n5\n7\n");
17. printf("Total 3 for length 1\n");
18. for(i=2;i<=MAX_N;i++){
19. new_list->clear();
20. v*=10;
21. THE_LIST::iterator it;
22. for(it=orig_list->begin();it!=orig_list->end();++it){
23. integer& u=*it;
24. for(j=1;j<=9;j++){
25. integer cur(j*v+u);
26. if(CHugeInt(cur).IsPrime()){
27. new_list->push_back(cur);
28. printf("%s\n",cur.GetStrA(FS_NORMAL));
29. count++;
30. }
31. }
32. }
33. printf("Total %d for length %d\n",new_list->size(),i);
34. if(new_list->size()==0)break;
35. tmp_list=orig_list;
36. orig_list=new_list;
37. new_list=tmp_list;
38. }
39. printf("Total %d found\n",count);

复制代码

无心人

是啊 题目有趣而已 外的有限 内的可能是无限吧 猜测的

mathe

内的更少，稍微修改一下代码就出来了: Call HugeCalc V8.0.0.0 3 5 7 Total 3 for length 1 31 37 53 59 71 73 79 Total 7 for length 2 311 313 317 373 379 593 599 719 733 739 797 Total 11 for length 3 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393 Total 11 for length 4 31193 31379 37337 37339 37397 59393 59399 71933 73331 73939 Total 10 for length 5 373379 373393 593933 593993 719333 739391 739393 739397 739399 Total 9 for length 6 3733799 5939333 7393913 7393931 7393933 Total 5 for length 7 37337999 59393339 73939133 Total 3 for length 8 Total 0 for length 9 Total 59 found

mathe

发现问题了，无心人的定义是不需要无限制剥下去的。只需要剥一层。如果这样，结果应该非常多。 我上面是当成可以无限剥下去的了。