数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 6463|回复: 29

[擂台] 洋葱素数

[复制链接]
发表于 2008-4-3 08:06:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

现在求小于等于10^19的全部这类数字
=================================================
高中用计算器算过,挺好玩的一个东西
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-3 08:12:51 | 显示全部楼层
内洋葱素数很好处理
除最高位外数字都是1, 3, 7, 9,最高位是3, 5, 7, 9
外洋葱素数组合多的多,但最低位必须是3, 7, 9
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 08:30:42 | 显示全部楼层
惨了,这个版块快成了素数专辑了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-3 08:54:17 | 显示全部楼层
等我再出一个容易的问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 16:51:20 | 显示全部楼层
mathe说一下算法吧.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 17:03:50 | 显示全部楼层
这个基本上算不上什么算法,简单从短的向长的构造就可以了。
先是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

  9.    int i,j;
  10.     integer v(1);
  11.     int count=3;
  12.     list1.push_back(integer(3));list1.push_back(integer(5));list1.push_back(integer(7));
  13.     orig_list=&list1;
  14.     new_list=&list2;
  15.     printf("3\n5\n7\n");
  16.     printf("Total 3 for length 1\n");
  17.     for(i=2;i<=MAX_N;i++){
  18.         new_list->clear();
  19.         v*=10;
  20.         THE_LIST::iterator it;
  21.         for(it=orig_list->begin();it!=orig_list->end();++it){
  22.             integer& u=*it;
  23.             for(j=1;j<=9;j++){
  24.                 integer cur(j*v+u);
  25.                 if(CHugeInt(cur).IsPrime()){
  26.                     new_list->push_back(cur);
  27.                     printf("%s\n",cur.GetStrA(FS_NORMAL));
  28.                     count++;
  29.                 }
  30.             }
  31.         }
  32.         printf("Total %d for length %d\n",new_list->size(),i);
  33.         if(new_list->size()==0)break;
  34.         tmp_list=orig_list;
  35.         orig_list=new_list;
  36.         new_list=tmp_list;
  37.     }
  38.     printf("Total %d found\n",count);
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-3 17:08:04 | 显示全部楼层

是啊
题目有趣而已
外的有限
内的可能是无限吧
猜测的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-3 17:13:16 | 显示全部楼层
发现问题了,无心人的定义是不需要无限制剥下去的。只需要剥一层。如果这样,结果应该非常多。
我上面是当成可以无限剥下去的了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-7-26 18:33 , Processed in 0.288755 second(s), 19 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表