求测试下面程序以及一连串的问题
因为原题不是正式版~把题目贴出来不太好看，我还是简单描述一下算了~题目很简短--判断2^62范围内的质数,是就输出yes,不是就输出no
我自己写了个，但由于AC32位不支持long long 型，无法进行高位测试,想知道高位极限测试效率如何~
程序代码：/*题目,判断2^62范围内的质数--效率至上!!!(我vc不支持long long 型,固无法进行高位测试--有兴趣的可以改改数据类型)*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STEP 10//选取推导循环步长周期的质数基数(在允许的范围内,STEP越大,遍历时间越短(但预备时间越长),STEP最好不要超过11(不要低于4))
int fun(char *b,int s[]);//求每个步长
int sum(int s[]);//求周期数
void set(int s[]);//求质数基数以及每个质数的数值
int judge_1(int s[],int n);
int judge_2(int s[],int n);
int judge_3(int s[],int n);
int judge_1(int s[],int n)
{
int i=0;
for (i=0;i<STEP-3;i++)
if (n%s[i]==0)
return 0;
return 1;
}
int judge_2(int s[],int n)
{
int i=0;
for (i=0;i<STEP-2;i++)
if (n==s[i])
return 1;
return 0;
}
int judge_3(int s[],int n)
{
int i=0;
for (i=0;i<STEP-2;i++)
if (n%s[i]==0)
return 1;
return 0;
}
int fun(char *b,int s[])
{
int i=0;
int a=s[STEP-2];
char *p=b;
int kk=sum(s);
for (i=s[STEP-1];i<=s[STEP-2]+kk;i++)
if (judge_1(s,i))
{
*p++=i-a;//这里用指针能提高运行效率
a=i;
}
return p-b;
}
void set(int s[])
{
int i=0;
int j=0;
int k=0;
for (i=2;k<STEP;i++)
{
for (j=2;j<=(int)sqrt(i);j++)
if (i%j==0)
break;
if (j==(int)sqrt(i)+1)
s[k++]=i;
}
}
int sum(int a[])
{
int i=0;
int sum=1;
for (i=0;i<STEP-3;i++)
sum*=a[i];
return sum;
}
int main()
{
char *a=NULL;//char 型看完程序框架分析知道,char型其实存放小数据,能节省空间(虽然还是浪费了不少空间)~
int step=0;
int s[STEP]={0};
int n=0;
int i=0;
int flag=0;
set(s);//求质数基数以及每个质数的数值
a=(char *)calloc(sum(s),sizeof(char));//使用动态内存分配能最大限度减少空间损失
step=fun(a,s);
while (scanf("%d",&n)!=EOF)
{
char *p=NULL;//用指针提高运行效率
flag=1;
if (n<2)
flag=0;
else if (judge_2(s,n))
flag=1;
else if (judge_3(s,n))
flag=0;
for (i=s[STEP-2],p=a;i<=(int)sqrt(n)&&flag;i+=*p++)
{
if (n%i==0)
flag=0;
if (p==a+step)
p=a;
}
if (flag)
printf("yes\n");
else
printf("no\n");
}
free(a);
return 0;
}下面有几个我想解决的问题:
首先，接受极限测试得先把关键数据改为long long 型~
1:算法有没有问题~结果是否会出错~
2:设STEP=10或者STEP=11如果题目要求每组测试数据要在1s内得出正确结果~极限测试会不会超时~
3:STEP 取值感觉取7到11的执行效率都差不多~是不是STEP对执行效率影响不大~还有STEP的最佳取值为多少~
4:听说用指针遍历数组能提高执行效率~但初步尝试用数组和指针效率差不多~事实是不是这个样子的~
5:对这题有没有什么较好的算法~可以拿出来交流一下~
[此贴子已经被作者于2017-1-9 22:11编辑过]
算法还是以四楼为佳~有时间我尽量写详细注释。大体思路是这样的，判断质数要尽量减少耗时，只需判断它是否被小于它的一个质数（不等于1）整除，尽量跳开合数判断。例如，只需判断该数是否能被2 3 5 7 11……整除~以上面5个参与整除的质数为例，2*3*5*7*11为一个判断周期，在一个判断周期里面，跳过被2 3 5 7 11自身及其整除的合数就行了，然后再进一步筛选~思路应该不难理解
我想有你这个思想基础下我的算法就容易理解多了~其实预先从文件读入一个素数表(1000w内的质合比约为1:16，2^31--20多亿的质合比应该更低，估计素数在10000w左右)效率最佳(可惜AC不允许文件读入
)~