在作
数素数 (20 分) Pi表示第 i 个素数。现任给两个正整数 M≤N≤10^4 ,请输出 P M 到 P N 的所有素数
这一题时,
使用了构造素数数组的方法,
之后每次在判断obj是否为素数时,只需要拿素数表中的数来判断即可,如果obj是素数,则也加入这个素数表中。
可是提交后发现这一方法超时
随后网络搜索解答发现判断obj是否为素数时,直接使用2到sqrt(obj)来逐一判断反而可以通过。
因不解故来询问一下
#include <stdio.h>
void printall( int N, int M, int*prime, int size );
int isprime( int obj, int* prime, int size );
int main ()
{
int N = 0;
int M = 0;
scanf("%d %d",&M,&N); //要求输出第M到第N个素数
int prime[N]; //素数表
prime[0] = 2;
int size = 1; //素数表中的素数数量
int obj = 3;
while( size<N ) {
if( isprime(obj, prime, size) ) { //判断obj是否为素数
prime[size] = obj;
size++;
}
obj += 2;
}
printall( N, M, prime, size );//按题目要求输出
return 0;
}
void printall( int N, int M, int*prime, int size ) {
for( int i = 0; i<size; i++ ) {
if( i>=M-1 && i<N ) {
printf("%d",prime[i]);
if( i!=N-1 )
printf("%c",(i+2-M)%10 == 0?'\n':' ');}
}
}
int isprime( int obj, int* prime, int size ) {
int flag = 1;
for( int i = 0; i<size; i++ ) {
if( obj%prime[i] == 0 ) {
flag = 0;
break;
}
}
return flag;
}
以上是使用素数表求解的全部代码
接下来将isprime()函数替换为直接求解的方式,反而得到了通过
int isprime( int obj ) {
int flag = 1;
for( int i = 2; i<=sqrt(obj); i++ ) {
if( obj%i == 0 ) {
flag = 0;
break;
}
}
return flag;
}