马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目如下:
【描述】 我们想知道第几个素数是什么数字。怎样子可以快速地给出第N个素数呢?1<=N<=50000。注意:本题判断某个数x是否为素数如果采用从2, ..., x-1 取模是否为0来判断会超时,有效的方法是对[2, sqrt(x)]内的整数取模判断即可,sqrt函数须包含math头文件。本题某些数据比较大你可能需要用到 long 的数据类型。
【输入】 输入的第一行代表T个测试样例,接下来的T行的每一行代表第N个素数。 【输出】 T行, 每行输出对应的第N个素数。
我的代码如下: #include <stdio.h>
#include <math.h>
int main(){
int N=50000;
long int i, prime[N];
int m=4,j,x=2;
prime[0]=2;
prime[1]=3;
for (;m<620000;m++){
for (j=2; j<=sqrt(m); j++){
if ((m % j)==0){
break;
}
}
prime[x]=m;
x++;
}
int T,num;
scanf("%d", &T);
int z=0;
for (;z<T;z++){
scanf ("%d",&num);
printf("%d\n",prime[num-1]);
}
return 0;
}
这个代码运行时会发生runtime error....... 我是刚入门C语言的,不知道哪里有什么问题...希望各位大神帮我看看并指出!!谢谢!! 
本帖最后由 jackz007 于 2019-11-4 16:24 编辑
runtime error 的原因是数组 prime[] 的空间开小了,导致下标越界。在给定的数值范围内,一共有 50612 个素数,可是, prime[] 只定义了 50000 个元素,怎么能不出错?
只要把 N 的数值从 50000 改到 51000 就可以解决问题。
下面是我修改的代码,楼主可以参考一下:
- #include <stdio.h>
- #include <math.h>
- #define N 51000
- int main(){
- unsigned int i , j , k , m , n , prime[N] ;
- bool f ;
- for(m = 0 , k = 0 ; k < 620000 ; k ++) {
- f = false ;
- if(k > 0) for (f = true , j = 2 ; j < (int) sqrt(k + 1) + 1 && f ; j ++) if(!((k + 1) % j)) f = false ;
- if(f) prime[m ++] = k + 1 ;
- }
- printf("m = %d\n" , m) ;
- scanf("%d" , & n) ;
- for(k = 0 ; k < n ; k ++) {
- printf("\n") ;
- scanf("%d" , & j) ;
- if(j <= m) printf("%d\n" , prime[j - 1]) ;
- else printf("out of data index!\n") ;
- }
- }
复制代码
|