用数组查找第N个素数
题目如下：【描述】我们想知道第几个素数是什么数字。怎样子可以快速地给出第N个素数呢？1<=N<=50000。注意：本题判断某个数x是否为素数如果采用从2, ..., x-1 取模是否为0来判断会超时，有效的方法是对内的整数取模判断即可，sqrt函数须包含math头文件。本题某些数据比较大你可能需要用到 long 的数据类型。
【输入】 输入的第一行代表T个测试样例，接下来的T行的每一行代表第N个素数。【输出】 T行， 每行输出对应的第N个素数。
我的代码如下：#include <stdio.h>
#include <math.h>
int main(){
int N=50000;
long int i, prime;
int m=4,j,x=2;
prime=2;
prime=3;
for (;m<620000;m++){
for (j=2; j<=sqrt(m); j++){
if ((m % j)==0){
break;
}
}
prime=m;
x++;
}
int T,num;
scanf("%d", &T);
int z=0;
for (;z<T;z++){
scanf ("%d",&num);
printf("%d\n",prime);
}
return 0;
}
这个代码运行时会发生runtime error.......我是刚入门C语言的，不知道哪里有什么问题...希望各位大神帮我看看并指出！！谢谢！！{:9_221:}
第一个for循环是求出素数然后储存在数组中；
第二个for循环是查找第N个素数 本帖最后由 LOYISHEN 于 2019-11-4 16:18 编辑
原因在于你设置数组长度的时候使用了变量来作为数组的大小，也就是 int N = 50000 跟后面 long int prime 这两个地方的问题
在C语言中，定义数组长度不可以使用变量，只能使用常量，比如 int prime 这种的。
或者，你可以使用宏定义 #define N 50000 , 然后 long int prime 这个就没问题了，因为这里的N会被编译器替换为常量 50000。
给你改了一下这里的代码（后面的没看）：
#include <stdio.h>
#include <math.h>
#define N 50000
int main(){
long int i, prime;
int m=4,j,x=2;
prime=2;
prime=3;
for (;m<620000;m++){
for (j=2; j<=sqrt(m); j++){
if ((m % j)==0){
break;
}
}
prime=m;
x++;
}
int T,num;
scanf("%d", &T);
int z=0;
for (;z<T;z++){
scanf ("%d",&num);
printf("%d\n",prime);
}
return 0;
}
或者你也可以直接在数组长度里面写一个常量 50000，就像我上面所说的那样 long int prime。
在代码层面上能发现这个问题，但没有看你的算法。
完 本帖最后由 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 ;
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 = 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) ;
else printf("out of data index!\n") ;
}
} jackz007 发表于 2019-11-4 16:14
runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 5061 ...
啊啊啊太感谢了！！原来是越界了..........
谢谢大神！！ jackz007 发表于 2019-11-4 16:14
runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 5061 ...
#include <stdio.h>
#include <math.h>
#define N 51000
int main(){
unsigned int i , j , k , m , n , prime ;
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 = 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) ;
else printf("out of data index!\n") ;
}
}
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(8) : error C2065: 'bool' : undeclared identifier
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(8) : error C2146: syntax error : missing ';' before identifier 'f'
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(8) : error C2065: 'f' : undeclared identifier
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(10) : error C2065: 'false' : undeclared identifier
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(11) : error C2065: 'true' : undeclared identifier
c:\program files (x86)\microsoft visual studio\myprojects\lianxi9\lianxi9.c(11) : warning C4018: '<' : signed/unsigned mismatch
执行 cl.exe 时出错.
lianxi9.obj - 1 error(s), 0 warning(s)
大神，为什么我的Vc++6.0无法运行你的这个程序，小白求助 谁能不死 发表于 2019-11-5 08:50
#include
#include
bool 是 C++ 才有的数据类型，你把源程序文件的扩展名由 ".c" 改成 ".cpp" 再编译试试看呢。
如果有警告，可以在 main() 函数尾部添加一个 return 0 ; 的语句。
下面是我用 VC6 编译的实况：
C:\Bin>cl x.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8804 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
x.cpp
Microsoft (R) Incremental Linker Version 6.00.8447
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.
/out:x.exe
x.obj
C:\Bin> jackz007 发表于 2019-11-5 11:23
bool 是 C++ 才有的数据类型，你把源程序文件的扩展名由 ".c" 改成 ".cpp" 再编译试试看呢。
...
{:7_146:}{:7_146:}{:7_146:}
大神 确实厉害 ；就文件扩展名改成.cpp后加个return 0；就完美了 jackz007 发表于 2019-11-4 16:14
runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 5061 ...
/*大神 有空时再帮我看看这个程序， 错误提示是if ( prime(n) )错误C2065:“prime”：未声明的标识符
*/
# include <stdio.h>
bool Prime( int val)
{
inti;
for (i=2; i<val; ++i)
{
if (0 == val%i)
break;
}
if(i == val)
return true;
else
return false;
}
int main(void)
{
int n;
printf("请输入你要检验的数字\n");
scanf("%d",n);
if ( prime(n) )
printf("%d这个数是素数\n", n);
else
printf("%d这个数不是素数\n", n);
return 0;
}
谁能不死 发表于 2019-11-5 17:28
/*大神 有空时再帮我看看这个程序， 错误提示是if ( prime(n) )错误C2065:“prime”：未声明的标识符 ...
if ( prime(n) )
你的函数定义里 P 是大写字母
if ( Prime(n) ) jackz007 发表于 2019-11-5 17:52
if ( prime(n) )
你的函数定义里 P 是大写字母
if ( Prime(n) )
非常感谢！
页:
[1]