PAT Basic 1007. 素数对猜想 (20) (C语言实现) | PAT Solution in C

[xlucn]

https://oliverlew.github.io/PAT/Basic/1007.html

题目

[yanzi-wu]

开始以为27行应该为if(iPrimeMinus2==1&&iPrimeMinus1==0),后来以为完全没必要，想了半天才想通，不可能出现三个连续的素数。对于数组primes的大小问题，19行i足够大时会不会超出数组空间。

[yanzi-wu]

开始以为27行应该为if(iPrimeMinus2==1&&iPrimeMinus1==0),后来以为完全没必要，想了半天才想通，不可能出现三个连续的素数。对于数组primes的大小问题，19行j足够大时会不会超出数组空间。

[xlucn]

@z1206138982
开始以为27行应该为if(iPrimeMinus2==1&&iPrimeMinus1==0),后来以为完全没必要，想了半天才想通，不可能出现三个连续的素数。对于数组primes的大小问题，19行i足够大时会不会超出数组空间。

其实我这个思路有些繁琐了：这个素数数组只是用于验证更大的素数的，也就是说，要验证i，只需要验证i能否被sqrt(i)内的素数整除。然后估算sqrt(100000)之内的素数个数，其实是不超过100的，这个数组只需放这些数就好了。

[yanzi-wu]

@OliverLew

@z1206138982
开始以为27行应该为if(iPrimeMinus2==1&&iPrimeMinus1==0),后来以为完全没必要，想了半天才想通，不可能出现三个连续的素数。对于数组primes的大小问题，19行i足够大时会不会超出数组空间。

其实我这个思路有些繁琐了：这个素数数组只是用于验证更大的素数的，也就是说，要验证i，只需要验证i能否被sqrt(i)内的素数整除。然后估算sqrt(100000)之内的素数个数，其实是不超过100的，这个数组只需放这些数就好了。

董了

[ShaobinChen-AH]

有一个测试点发生段错误，怎么也找不到原因？求指点，代码如下：

#include<stdio.h>
int main()
{
    int N,a[100000]={0},b[100000]={0},cnt=0,count=0;
    int i,j;
    scanf("%d\n",&N);
    for(i=2;i<=N;i++)
    {
        if(a[i]==1) continue;
        b[cnt++]=i;
        for(j=i*i;j<=N;j+=i)
           a[j]=1;
    }
    for(int k=0;k<cnt-1;k++)
    {
        if(b[k+1]-b[k]==2) count++;
    }
    printf("%d\n",count);
    return 0;
}

[xlucn]

@csb-github
有一个测试点发生段错误，怎么也找不到原因？求指点，代码如下：

    for(i=2;i<=N;i++)
...
        for(j=i*i;j<=N;j+=i)

应该是j溢出了，变成负值

P.S. markdown代码可用```（行间）或者`（行内）括起来，更具可读性。

[ShaobinChen-AH]

谢谢你的答疑！看到你的回复，我尝试了能否只做小的改动，得到正确的代码，不过目前还是没成功（还是最后一个测试点出现段错误），我再想想看吧。 | | chenshaobin000001 | | chenshaobin000001@163.com | 签名由网易邮箱大师定制 在2020年2月18日 20:39，LuXu<notifications@github.com> 写道： @csb-github 有一个测试点发生段错误，怎么也找不到原因？求指点，代码如下： for(i=2;i<=N;i++) ... for(j=i*i;j<=N;j+=i) 应该是j溢出了，变成负值 P.S. markdown代码可用```（行间）或者`（行内）括起来，更具可读性。 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.