直接试除还是挺快的:
#include
using namespace std;
using namespace LiDIA;
#define HPRIME 1000
int primelist;
int pc;
void initp()
{
int i,j;
primelist=primelist=1;
...
mathe 发表于 2009-8-26 11:27 http://bbs.emath.ac.cn/images/common/back.gif
mathe的using namespace LiDIA;
程序中使用了 LiDIA的什么？怎么没看出来:Q:
可以把那行去掉。
因为 mathe 曾用 LiDIA 进行因数分解，改变算法后忘了去掉它了。
另外，我用 VS2008 编译 47# 的代码，需要将第 36 行代码由printf("%lld=%lld*%lld\n",r,primelist,r/primelist);改成printf("%lld=%d*%d\n",r,primelist,r/primelist);才能正确输出。
52# gxqcn
原来如此。
本帖最后由 〇〇 于 2009-8-27 08:51 编辑
47# mathe
我用你的算法改写的vc版本，怎么出来252个结果？
#include <stdio.h>
#include <conio.h>
//#include <windows.h>
#include "2M.txt"
void output(int *p); //输出函数
void permutation(int *p);//全排列函数
void test(__int64 r);
int a[]={0,1,2,5,6,7};//待排列数组
int N=sizeof(a)/sizeof(int); //数组长度
int *p=a; //数组指针
int n=0;
int m;
void test(__int64 r)
{
int i;
for(i=0;i<141800;i++){///skip prime 2 and 3
if(prime>=1900000)return;
if(r%prime==0)break;
}
if(prime<10000)return;
printf("%I64d=%d*%d\n",r,prime,r/prime);
}
void main()
{
output(p);
permutation(p); //调用全排列函数
__int64 r=189e8;
for(int i=0;i<720;i++)
test(r+m*100+43);
//output(p); //输出排列结果
//getch();
}
void permutation(int *p)
{
bool flag=false; //标志排列是否结束
int temp; //临时变量,用来交换数组元素
while(1)
{
for(int i=0;i<N-1;i++)
{
flag=true; //如已排列完,falg为真
if(p<p) //如果发现第一个倒序的数组元素,p被称为倒序元素
{
flag=false; //说明未排列完
int j=0;
while(p>=p); //找到第一个大于或等于倒序元素的数组元素
j-=1;
temp=p; //交换这两个元素
p=p;
p=temp;
j=0;
while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素
{
temp=p;
p=p;
p=temp;
j++;
}
break; //跳出for循环,
}
}
if(flag) //如果排列完,结束循环
break;
output(p); //输出排列结果
}
}
void output(int *p)
{
int s=0;
for(int i=0;i<N;i++)
s=s*10+p;
m=s;
//printf("%06d",s);
//printf("\n");
}
你的素数列表有问题.我的要求的是2开始的素数列表
55# mathe
为什么不是10000开始的质数呢？不是说其中一个为5位数？
因为若用试除法，
得先排除有小于10000的小因子的情形，
如果你的素数表缩水了，将无法进行该过程。
57# gxqcn
你的意思是说
我的结果中有的除数是质数，商是合数？
right!
我明白了，如果一个电话号码没有比10000小的质因数，而又有一个比10000大的质因数，那么除以其得到的商一定也是质数
这里用到了电话号码<19e10的条件