Counting fractions

TimeLimit: 2000MS  MemoryLimit: 65536 Kb

Totalsubmit: 39   Accepted: 6  

Description

Consider the fraction, n/d, where n and d are positive integers. If n <= d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d <= x?

Input

The input will consist of a series of x, 1 < x < 1000001.

Output

For each input integer x, you should output the number of elements contained in the set of reduced proper fractions for d <= x in one line.

Sample Input

3

8

Sample Output

3
21

Hint

HCF代表最大公約數

注意：關于數論的題很容易超過int類型的范圍，多考慮用long long類型。
歐拉函數請參閱：http://zh.wikipedia.org/zh-cn/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

代碼
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LEN 1100010
using namespace std;
int len0 = (int)sqrt(LEN);
int isp[LEN];//isprime?
int pr[LEN];//依次記錄素數
int pct;// prime count
long long rs[LEN];//fi(n)
int main()
{
    int i, j;
    int x;
    memset(isp, -1, sizeof(isp));
    for(int i = 2; i <= len0; i++)//素數篩法選出素數
    {
        if(isp[i])
        {
            for(int j = i * 2; j < LEN; j += i)
                isp[j] = 0;
        }
    }
    pct = 0;
    for(int i = 2; i < LEN; i++)//記下選出的素數
        if(isp[i])
            pr[pct++] = i;

    for(int i = 0; i < LEN; i++)
        rs[i] = i;
    for(int i = 0; i < pct; i++)
    {
        rs[pr[i]]--;
        for(int j = pr[i] * 2; j < LEN; j += pr[i])
        {
            rs[j] = rs[j]  / pr[i] * (pr[i] - 1);//rs[]要定義成long long類型，因為計算過程中乘法會超過int類型的取值范圍
            //rs[j] -= rs[j] / pr[i];
        }
    }
    while(scanf("%d", &x) != EOF)
    {
        long long sum = 0;
        for(int i = 2; i <= x; i++)
            sum += rs[i];
        //printf("%lld\n", sum);
        cout << sum << endl;//用cout輸出，不用考慮使用%lld還是%I64d
    }
    //system("pause");
    return 0;
}