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 <iostream>
using namespace std;
const int right = 5000002;
bool isPrime[5000002];
int primeList[5000002];
int phi[5000002];
int main(void)
{
    int primeCount = 0;
    int L, R;
    cin >> L >> R;
    for(int i = 1; i <= R; i++)
    {
        isPrime[i] = true;
    }
    for(int i = 2; i <= R; i++)
    {
        if(isPrime[i])
        {
            primeCount = primeCount + 1;
            primeList[primeCount] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= primeCount; j++)
        {
            if(i*primeList[j] > R)
            {
                break;
            }
            isPrime[i*primeList[j]] = false;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX