无心人 发表于 2008-4-3 08:06:21

洋葱素数

比较有趣的题目假设一个素数去掉十进制最高位一个数字还是素数，称外洋葱素数
假设一个素数去掉十进制最低位一个数字还是素数，称内洋葱素数

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

无心人 发表于 2008-4-3 08:12:51

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

gxqcn 发表于 2008-4-3 08:30:42

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

无心人 发表于 2008-4-3 08:54:17

等我再出一个容易的问题

mathe 发表于 2008-4-3 16:39:00

外洋葱:
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 发表于 2008-4-3 16:51:20

mathe说一下算法吧.

mathe 发表于 2008-4-3 17:03:50

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

   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);

无心人 发表于 2008-4-3 17:08:04

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

mathe 发表于 2008-4-3 17:11:24

内的更少，稍微修改一下代码就出来了:
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 发表于 2008-4-3 17:13:16

发现问题了，无心人的定义是不需要无限制剥下去的。只需要剥一层。如果这样，结果应该非常多。
我上面是当成可以无限剥下去的了。
页: [1] 2 3
查看完整版本: 洋葱素数