[已解决]用数组查找第N个素数

numuaayebo

题目如下：

【描述】

我们想知道第几个素数是什么数字。怎样子可以快速地给出第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:14:20

      runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 50612 个素数，可是， prime[] 只定义了  50000 个元素，怎么能不出错？
      只要把 N 的数值从 50000 改到 51000 就可以解决问题。
      下面是我修改的代码，楼主可以参考一下：

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define N 51000
   
5. 
   
6. int main(){
   
7.         unsigned int i , j , k , m , n , prime[N]                                                                     ;
   
8.         bool f                                                                                                        ;
   
9.         for(m = 0 , k = 0 ; k < 620000 ; k ++) {
   
10.                 f = false                                                                                             ;
    
11.                 if(k > 0) for (f = true , j = 2 ; j < (int) sqrt(k + 1) + 1 && f ; j ++) if(!((k + 1) % j)) f = false ;
    
12.                 if(f) prime[m ++] = k + 1                                                                             ;
    
13.         }
    
14.         printf("m = %d\n" , m)                                                                                        ;
    
15.         scanf("%d" , & n)                                                                                             ;
    
16.         for(k = 0 ; k < n ; k ++) {
    
17.                 printf("\n")                                                                                          ;
    
18.                 scanf("%d" , & j)                                                                                     ;
    
19.                 if(j <= m) printf("%d\n" , prime[j - 1])                                                              ;
    
20.                 else printf("out of data index!\n")                                                                   ;
    
21.         }
    
22. }

复制代码

跳转到最佳答案楼层

numuaayebo

第一个for循环是求出素数然后储存在数组中；
第二个for循环是查找第N个素数

LOYISHEN

原因在于你设置数组长度的时候使用了变量来作为数组的大小，也就是 int N = 50000 跟后面 long int prime[N] 这两个地方的问题

在C语言中，定义数组长度不可以使用变量，只能使用常量，比如 int prime[1000] 这种的。

或者，你可以使用宏定义 #define N 50000 , 然后 long int prime[N] 这个就没问题了，因为这里的N会被编译器替换为常量 50000。

给你改了一下这里的代码（后面的没看）：

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define N 50000
   
5. 
   
6. int main(){
   
7.     long int i, prime[N];
   
8.     int m=4,j,x=2;
   
9.     prime[0]=2;
   
10.     prime[1]=3;
    
11.     for (;m<620000;m++){
    
12.         for (j=2; j<=sqrt(m); j++){
    
13.             if ((m % j)==0){
    
14.                 break;
    
15.             }
    
16.         }
    
17.         prime[x]=m;
    
18.         x++;
    
19.     }
    
20.      int T,num;
    
21.     scanf("%d", &T);
    
22.     int z=0;
    
23.     for (;z<T;z++){
    
24.         scanf ("%d",&num);
    
25.         printf("%d\n",prime[num-1]);
    
26.         }
    
27.     return 0;
    
28. }

复制代码

或者你也可以直接在数组长度里面写一个常量 50000，就像我上面所说的那样 long int prime[50000]。

在代码层面上能发现这个问题，但没有看你的算法。

完

jackz007

      runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 50612 个素数，可是， prime[] 只定义了  50000 个元素，怎么能不出错？
      只要把 N 的数值从 50000 改到 51000 就可以解决问题。
      下面是我修改的代码，楼主可以参考一下：

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define N 51000
   
5. 
   
6. int main(){
   
7.         unsigned int i , j , k , m , n , prime[N]                                                                     ;
   
8.         bool f                                                                                                        ;
   
9.         for(m = 0 , k = 0 ; k < 620000 ; k ++) {
   
10.                 f = false                                                                                             ;
    
11.                 if(k > 0) for (f = true , j = 2 ; j < (int) sqrt(k + 1) + 1 && f ; j ++) if(!((k + 1) % j)) f = false ;
    
12.                 if(f) prime[m ++] = k + 1                                                                             ;
    
13.         }
    
14.         printf("m = %d\n" , m)                                                                                        ;
    
15.         scanf("%d" , & n)                                                                                             ;
    
16.         for(k = 0 ; k < n ; k ++) {
    
17.                 printf("\n")                                                                                          ;
    
18.                 scanf("%d" , & j)                                                                                     ;
    
19.                 if(j <= m) printf("%d\n" , prime[j - 1])                                                              ;
    
20.                 else printf("out of data index!\n")                                                                   ;
    
21.         }
    
22. }

复制代码

numuaayebo

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[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")                                                                   ;
        }
}

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无法运行你的这个程序，小白求助

jackz007

谁能不死 发表于 2019-11-5 08:50
#include
#include

      bool 是 C++ 才有的数据类型，你把源程序文件的扩展名由 ".c" 改成 ".cpp" 再编译试试看呢。
      如果有警告，可以在 main() 函数尾部添加一个 return 0 ; 的语句。

      下面是我用 VC6 编译的实况：

1. C:\Bin>cl x.cpp
   
2. Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8804 for 80x86
   
3. Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
   
4. 
   
5. x.cpp
   
6. Microsoft (R) Incremental Linker Version 6.00.8447
   
7. Copyright (C) Microsoft Corp 1992-1998. All rights reserved.
   
8. 
   
9. /out:x.exe
   
10. x.obj
    
11. 
    
12. C:\Bin>

复制代码

谁能不死

jackz007 发表于 2019-11-5 11:23
bool 是 C++ 才有的数据类型，你把源程序文件的扩展名由 ".c" 改成 ".cpp" 再编译试试看呢。
   ...

大神 确实厉害 ；就文件扩展名改成.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)
{
        int  i;
       
        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;
}

jackz007

谁能不死 发表于 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) )

非常感谢！