七彩素数问题

northwolves

原帖由 gxqcn 于 2008-12-23 09:51 发表
有两种方案：

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

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

通过组合算法， 3*6!=2160 个候选数，末尾不能是2，4，5，6

无心人

我想知道你的程序代码？

我这个问题就看代码的精巧程度

northwolves

我的代码：

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. }

复制代码

无心人

很好很强大

gxqcn

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

疑问：not_prime、count 变量未作初始化=0，不知在不同的编译器上行为是否一致？

mathe

如果求所有的十进制表示中所有位上数字都不相同的素数呢？

无心人

肚子
我不懂

我的理解，你想求素数，且各位数字互不相等？
我想
1、最多8位
2、组成各位数字的数字和应该不能是3的倍数

无心人

另外， 我觉得
STL固然好
但C能用链表实现个简洁的算法

gxqcn

犯不着用链表，数组足矣。

无心人

链表不等于指针啊
线性表同样可以模拟链表