七彩素数问题

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

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

无心人

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