均是素数——天梯训练赛

L1-8 均是素数 (20 分)

在给定的区间 [m,n] 内，是否存在素数 p、q、r（p<q<r），使得 pq+r、qr+p、rp+q 均是素数？

输入格式：

输入给出区间的两个端点 0<m<n≤1000，其间以空格分隔。

输出格式：

在一行中输出满足条件的素数三元组的个数。

输入样例：

1 35

输出样例：

10

样例解读

满足条件的 10 组解为：

2, 3, 5
2, 3, 7
2, 3, 13
2, 3, 17
2, 5, 7
2, 5, 13
2, 5, 19
2, 5, 31
2, 7, 23
2, 13, 17

解题方法：如果这题采用线性筛对每个数进行逐一判断，就会出现超时现象，因此这题采用更高级一点的方法 欧拉筛。

Code：

#include <iostream>
#include <stdio.h>

using namespace std;

const int N = 1000010;

int n, m, p, q, r, ans;
bool f[N];

void prime() //欧拉筛主体部分
{
    for(int i = 2; i <= 1000; i ++ )
    {
        if(!f[i])
        {
            for(int j = 2; i * j <= 1000010; j ++ )
            {
                if(!f[i * j])  f[i * j] = true;
            }
        }
    }
}

signed main()
{
    f[1] = true;
    prime();
    cin >> n >> m;
    for(int i = n; i <= m; i ++ )
    {
        for(int j = i + 1; j <= m; j ++ )
        {
            for(int k = j + 1; k <= m; k ++ )
            {
                if(!f[i] && !f[j] && !f[k] && !f[i * j + k] && !f[i * k + j] && !f[j * k + i])  ans ++;
            }
        }
    }
    cout << ans << endl;
}