消息关闭
    暂无新消息!

PAT考试1007. 素数对猜想 (20)

问题作者 : 瑞瑞2017-08-02发布
编译器上可以通过的。。。在提交的时候最后总是提示一个段错误,想请教大神是个什么情况。
-----------------------------------------------------------------------------------
/**
让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 10^5),请计算不超过N的满足猜想的素数对的个数。

输入格式:每个测试输入包含1个测试用例,给出正整数N。

输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。

输入样例:
20
输出样例:
4
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int limit = 0, prime[1000] = {0};
    int i = 0, j = 0, k = 0, l = 0, digit = 0;

    scanf("%d", &limit);

    if(limit > pow(10, 5))
        exit(0);

    for(i = 2; i <= limit; i ++)
    {
        for(j = 2; j < i; j ++)
        {
            if(i % j == 0)
            {
                break;
            }
        }
        if(j == i)
        {
            prime[k++] = i;
        }
    }
    for(l = 1; l < k; l ++)
    {
        if(prime[l] - prime[l-1] == 2)
            digit ++;
    }
    printf("%d", digit);

    return 0;
}

2个回答

︿ 1
 int limit = 0, prime[1000] = {0};
改为
 int limit = 0, 
static int prime[1000] = {0};

在占用内存空间较大的局部数组声明的前面加static将其从堆栈数据段挪到全局数据段即可避开因局部数组大小超过默认堆栈大小1MB造成程序不能正常运行的问题。
︿ 0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int limit = 0, *prime;
    int i = 0, j = 0, k = 0, l = 0, digit = 0;

    scanf("%d", &limit);

    prime = (int *)malloc(limit * sizeof(int));
    if (!prime)
        return -1;
    if(limit > pow(10, 5))
        exit(0);

    for(i = 2; i <= limit; i ++)
    {
        for(j = 2; j < i; j ++)
        {
            if(i % j == 0)
            {
                break;
            }
        }
        if(j == i)
            prime[k++] = i;
    }
    for(l = 0; l < k; l ++) {    /*这个地方是不是应该从0开始?*/
        if(prime[l] - prime[l-1] == 2)
            digit ++;
    }
    printf("%d", digit);

    return 0;
}