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

numuaayebo · 发表于 2019-11-4 14:15:01

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

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:14:20

本帖最后由 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")                                                                   ;
        }
}

跳转到最佳答案楼层

numuaayebo · 发表于 2019-11-4 14:18:55

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

LOYISHEN · 发表于 2019-11-4 16:03:11

本帖最后由 LOYISHEN 于 2019-11-4 16:18 编辑

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

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

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

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

#include <stdio.h>
#include <math.h>

#define N 50000

int main(){
    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;
}

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

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

完

jackz007 · 发表于 2019-11-4 16:14:20

这个最佳答案由 jackz007 给出，感谢 jackz007 的回答。

单击隐藏图章

本帖最后由 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")                                                                   ;
        }
}

numuaayebo · 发表于 2019-11-4 16:50:11

jackz007 发表于 2019-11-4 16:14
runtime error 的原因是数组 prime[] 的空间开小了，导致下标越界。在给定的数值范围内，一共有 5061 ...

啊啊啊太感谢了！！原来是越界了..........
谢谢大神！！

谁能不死 · 发表于 2019-11-5 08:50:15

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 11:23:56

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

谁能不死 · 发表于 2019-11-5 16:19:04

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

大神确实厉害；就文件扩展名改成.cpp后加个return 0；就完美了

谁能不死 · 发表于 2019-11-5 17:28:40

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:52:35

谁能不死发表于 2019-11-5 17:28
/*大神有空时再帮我看看这个程序，错误提示是 if ( prime(n) ) 错误C2065:“prime”：未声明的标识符 ...

      if ( prime(n) )
      你的函数定义里 P 是大写字母
      if ( Prime(n) )

谁能不死 · 发表于 2019-11-8 08:11:27

jackz007 发表于 2019-11-5 17:52
if ( prime(n) )
你的函数定义里 P 是大写字母
if ( Prime(n) )

非常感谢！

账号		自动登录	找回密码
密码			立即注册