洋葱素数

iii

假设一个素数去掉十进制最高位一个数字还是素数，称外洋葱素数
假设一个素数去掉十进制最低位一个数字还是素数，称内洋葱素数

现在求小于等于10^19的全部这类数字
=================================================
高中用计算器算过，挺好玩的一个东西

euogifubize

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

obibohazek

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

epezzaqegazeu

等我再出一个容易的问题

iciugun

外洋葱:
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

oliajazpafi

mathe说一下算法吧.

anadavetag

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

1. #include <list>using namespace std;....typedef CHugeInt integer;typedef list<integer> THE_LIST;THE_LIST list1,list2;THE_LIST *orig_list, *new_list, *tmp_list;#define MAX_N  50    int i,j;    integer v(1);    int count=3;    list1.push_back(integer(3));list1.push_back(integer(5));list1.push_back(integer(7));    orig_list=&list1;    new_list=&list2;    printf("3\n5\n7\n");    printf("Total 3 for length 1\n");    for(i=2;i<=MAX_N;i++){        new_list->clear();        v*=10;        THE_LIST::iterator it;        for(it=orig_list->begin();it!=orig_list->end();++it){            integer& u=*it;            for(j=1;j<=9;j++){                integer cur(j*v+u);                if(CHugeInt(cur).IsPrime()){                    new_list->push_back(cur);                    printf("%s\n",cur.GetStrA(FS_NORMAL));                    count++;                }            }        }        printf("Total %d for length %d\n",new_list->size(),i);        if(new_list->size()==0)break;        tmp_list=orig_list;        orig_list=new_list;        new_list=tmp_list;    }    printf("Total %d found\n",count);

复制代码

_only

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

ouukucakac

内的更少，稍微修改一下代码就出来了:
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

gocehuzana

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