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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5000000;
bool isPrime[N + 1];
int primeList[N + 1];
int phi[N + 1];
int primeCount = 0;
int main(){
    //freopen("input.txt", "r", stdin);
    int L, R;
    scanf("%d %d", &L, &R);
    memset(isPrime, true, sizeof isPrime);
    for (int i = 2; i <= R; ++i)
    {
        if (isPrime[i])
        {
            ++primeCount;
            primeList[primeCount] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= primeCount; ++j)
        {
            if (i*primeList[j] > R)
            {
                break;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX