PAT:1007 素数对猜想 (c语言版本)

不念不忘少年蓝@ 2023-05-28 11:15 87阅读 0赞

让我们定义d  
n  
 为：d  
n  
 =p  
n+1  
 −p  
n  
 ，其中p  
i  
 是第i个素数。显然有d  
1  
 =1，且对于n>1有d  
n  
 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

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

输入格式:  
输入在一行给出正整数N。

输出格式:  
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:  
20

输出样例:  
4

## 第一种方法：先找出全部素数然后比较 ##

#include <stdio.h>
    
    const int difference = 2;
    
    int isPrime(int n);
    
    int main()
    { 
        int i, k, n, len, count = 0;
        int a[100000];     //开的过小也可能会由点过不去
    
        scanf("%d", &n);
        for (k = 0, i = 2; i <= n; i++)   //不超过n，不要忘记等于号，否则会有一个点过不去
            if (isPrime(i))
                a[k++] = i;
        len = --k;
        for (i = 0; i < len; i++)
        { 
            if (a[i + 1] - a[i] == difference)
                count++;
        }
        printf("%d", count);
    
        return 0;
    }
    
    int isPrime(int n)
    { 
        int i;
    
        if (n <= 1)
            return 0;
        for (i = 2; i * i <= n; i++)
            if (n % i == 0)
                return 0;
    
        return 1;
    }

## 第二种方法边找边比较 ##

待补充//

发表评论取消回复

表情：

评论列表（有 0 条评论，87人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT~乙级~1007 素数对猜想 ~C++

题目描述：让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认

ゝ一世哀愁。/ 2023年10月11日 10:29/ 0 赞/ 9 阅读

相关 1007 素数对猜想

include<stdio.h> include<math.h> int main() { int n,a[100000],k,

旧城等待，/ 2023年10月09日 10:43/ 0 赞/ 100 阅读

相关 PAT B 1007 素数对猜想

1007 素数对猜想 (20分) 让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn

灰太狼/ 2023年07月04日 08:55/ 0 赞/ 49 阅读

相关 PAT 1007 素数对猜想

我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无

曾经终败给现在/ 2023年06月29日 07:29/ 0 赞/ 13 阅读

相关 PAT:1007 素数对猜想 (c语言版本)

让我们定义d n 为：d n =p n+1 −p n ，其中p i 是第i个素数。显然有d

不念不忘少年蓝@/ 2023年05月28日 11:15/ 0 赞/ 88 阅读

相关 PTA 1007 素数对猜想 (20分) C语言

1007 素数对猜想 (20分) 让我们定义d n 为：d n =p n+1 −p n ，其中p i

深藏阁楼爱情的钟/ 2022年11月27日 08:54/ 0 赞/ 208 阅读

相关 PAT 1007 素数对猜想

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

小咪咪/ 2022年08月18日 02:37/ 0 赞/ 202 阅读

相关 PAT乙级1007：素数对猜想

题目： ![70][] 解题思路： > 把不超过N的素数全部保存在容器中，再验证相邻素数的差值是否为2. 题解： include<iostrea

叁歲伎倆/ 2022年05月09日 12:28/ 0 赞/ 289 阅读

相关 PAT_B_1007 素数对猜想

题目描述：让我们定义dn 为：dn =pn+1 −pn ，其中pi 是第i个素数。显然有d1 =1，且对于n>1有d

爱被打了一巴掌/ 2021年11月01日 08:28/ 0 赞/ 384 阅读

相关 PAT 1007 素数对猜想 (20 分)（Java）

题目描述： ![在这里插入图片描述][20190822202034429.png] 输入格式: 输入在一行给出正整数N。输出格式: 在一行中输出

我不是女神ヾ/ 2021年09月23日 05:50/ 0 赞/ 386 阅读