PAT-B] 1007. 素数对猜想 [数论]

链接：1007. 素数对猜想 (20)

题意

任意给一个小于$10^5$的正整数N，并要求在$( 0, N )$这个范围内，
找出满足以下条件的数对的总数：

  1. 两个数均是素数
  2. 两个数之间相差2

样例中的N为20。
满足条件的数对为：
3, 5， 5, 7， 11, 13， 17, 19
总计4对， 则输出4。

分析

题意中要求判断的数均为素数，而且给的N也并不大。所以直接暴力打表，把所有的素数存到数组中再处理也挺简单的。

题目要求的条件是相差为2，对于素数来说除了2之外就没有其他偶数了，所以这里我们可以直接对相邻的素数进行判断，如果相邻的还不行其他的也不用考虑了。

PS：如果是其他的OJ说明输入多组样例的话，把每次的结果存下来给下面的样例使用会快很多哦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
typedef long long LL;
int prime[100015];  // 增序存放素数
int flag[100015];   // 标记这个下标对应的数是否是素数
int idx = 0;        // 素数数组的下标
void init( int n ){
    // 初始化两个数组为 0
    memset( prime, 0, sizeof( prime ) );
    memset( flag, 0, sizeof( flag ) );
    for( LL i = 2; i < n + 10; i++ ){
        if( flag[i] )   continue;   // 非素数则不处理
        prime[ idx++ ] = i;     // 素数存入素数数组
        for( LL j = i * i; j < 100002; j += i ) // 将其倍数均标记为合数
            flag[j] = 1;
    }
}
int main()
{
    int N;
    while( ~scanf( "%d", &N ) ){
        init( N );
        int num = 0;
        for(int i = 2; prime[i] <= N; i++ ){
            // 依次遍历相邻的素数 看是否满足条件
            if( prime[i] - prime[i - 1] == 2 )
                num++;
        }
        printf( "%d\n", num );
    }
    return 0;
}

小结

处理出素数的方法有很多，可以多尝试尝试。

数论
PAT-B, 数论