All primes - ladder training competition

L1-8 Are prime numbers (20 branch )

In a given interval [m,n] Inside , Is there a prime p、q、r（p<q<r）, bring pq+r、qr+p、rp+q Are prime numbers ？

Input format ：

Enter the two endpoints of the given interval 0<m<n≤1000, Separated by spaces .

Output format ：

Output the number of prime triples that meet the conditions in one line .

sample input ：

1 35

sample output ：

10

Example interpretation

Satisfied 10 Group solution is ：

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

How to solve the problem ： If this question uses a linear sieve to judge each number one by one , There will be a timeout , So this question adopts a more advanced method Euler screen .

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() // Euler screen main part 
{
    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;
}