数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[擂台] 七彩素数问题

[复制链接]
发表于 2008-12-23 17:23:40 | 显示全部楼层
原帖由 gxqcn 于 2008-12-23 09:51 发表
有两种方案:

1、用筛法得到 [1234567, 7654321] 中所有的素数,共 422652 个,剔除含有0、8、9数字之一的数;

2、通过组合算法,依次得到 7!=5040 个候选数,而后逐一甄别是否为素数。


通过组合算法, 3*6!=2160 个候选数,末尾不能是2,4,5,6
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-23 21:45:36 | 显示全部楼层
我想知道你的程序代码?

我这个问题就看代码的精巧程度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 00:23:55 | 显示全部楼层
我的代码:
  1. #include<algorithm>
  2. #include <iostream>
  3. using namespace std;
  4. int not_prime[7654321];
  5. main(){
  6.     int i,j,count;
  7.     not_prime[3]=0;
  8.     for(i=3;i<2761;i+=2){
  9.         if(!not_prime[i]){
  10.             for(j=i*i;j<7654321;j+=2*i)
  11.                 not_prime[j]=1;
  12.         }
  13. }
  14. char a[]="1234567";
  15. do{
  16. i=atoi(a);
  17. if (i%2==1 && not_prime[i]==0){
  18. cout << i << "\n";
  19. count++;
  20. }}
  21. while(std::next_permutation(a,a+7));
  22. cout << count-1 << "\n";
  23. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 08:08:53 | 显示全部楼层


很好很强大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 08:11:36 | 显示全部楼层

回复 13# northwolves 的帖子

这段代码用到了 STL 编程,调用了 next_permutation 算法。
虽然经历了字串到数字间的倒腾(可能相对比较费时),但就代码来是够简洁的。

疑问:not_prime、count 变量未作初始化=0,不知在不同的编译器上行为是否一致?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 08:14:19 | 显示全部楼层
如果求所有的十进制表示中所有位上数字都不相同的素数呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 08:25:34 | 显示全部楼层
肚子
我不懂

我的理解,你想求素数,且各位数字互不相等?
我想
1、最多8位
2、组成各位数字的数字和应该不能是3的倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 08:26:45 | 显示全部楼层
另外, 我觉得
STL固然好
但C能用链表实现个简洁的算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 08:46:12 | 显示全部楼层
犯不着用链表,数组足矣。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 08:57:11 | 显示全部楼层


链表不等于指针啊
线性表同样可以模拟链表
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-12 13:34 , Processed in 0.056647 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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