TIOJ 1514 Problem D. 橫掃射擊場

[數論]

#include<stdio.h>
#include<cstring>
#include<math.h>
#include<vector>
using namespace std;
#define LL long long int
#define N 1000001
LL phi[N];
LL PHI[N];
bool seive[N];
vector<int> PRIME;
int main()
{
    //BUILD PHI TABLE;
    phi[1]=1;
    for(int lx=2;lx<=N-1;lx++)
    {
        if(!seive[lx])
        {
            phi[lx]=lx-1;
            PRIME.push_back(lx);
        }
        for(int ly=0;lx*PRIME[ly]<N;ly++)
        {
            seive[lx*PRIME[ly]]=1;
            if(lx%PRIME[ly]==0)
            {
                phi[lx*PRIME[ly]]=phi[lx]*PRIME[ly];
                break;
            }
            else
                phi[lx*PRIME[ly]]=phi[lx]*(PRIME[ly]-1);
        }
    }
    PHI[1]=phi[1];
    for(int lx=2;lx<=N-1;lx++)
        PHI[lx]=PHI[lx-1]+phi[lx];
    int II;
    while(scanf("%d",&II)&&(II>0))
        printf("%I64d\n",2*PHI[II]+1);
    return 0;
}