题目72：分母不超过一百万的最简真分数的集合中包含多少元素？

欧拉计划

Counting fractions

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 ≤ 1,000,000?

题目：

考虑分数 n/d, 其中 n 和 d 是正整数。如果 n<d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。

如果我们将 d ≤ 8 的最简真分数按照大小的升序列出来，我们得到：

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

可知该集合中共有 21 个元素。

d ≤ 1,000,000 的最简真分数集合中包含多少个元素？

jerryxjr1220

这题其实也是欧拉函数的扩展。
欧拉函数phi（n）定义了小于n的正整数与n互质的个数。
那么sum（phi（2~8））=21
同样，本题就是求解sum（phi（2~1000000））

from time import clock
start = clock()

def getPrime(n):
    primes = [True]*n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j] = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
        if trueprime:
            primelist.append(k)
    return primelist

def philist(n):
    primelist = getPrime(n)
    PHI = [0]*(n+1)
    for eachprime in primelist:
        PHI[eachprime] = eachprime - 1
    for i in range(len(primelist)):
        p = primelist[i]
        for k in range(p*p,n+1,p):
                PHI[k] = PHI[int(k/p)]*(p-1)
        for j in range(p*p,n+1,p*p):
            PHI[j] = PHI[int(j/p)]*p
    return PHI
plist = philist(1000000)

print(sum(plist))

end = clock()
print ('Time:%.3f sec' % (end-start))

303963552391
Time: 4.211 sec

久疤K

jerryxjr1220 发表于 2016-10-16 13:49
这题其实也是欧拉函数的扩展。
欧拉函数phi（n）定义了小于n的正整数与n互质的个数。
那么sum（phi（2~8 ...

厉害!!
但是过程有瑕疵:

def philist(n):
    primelist = getPrime(n)
    # 上面获取质数时要变成getPrime(n+1)

检验:
r(11) == r(10) + 10
而你的却是
r(11) == r(10)
因为在边界处恰好为质数, 你没有获取到, 造成phi[11] = 0
上面的BUG只有在边界为质数时显示.
另外, 共享个比较高效的获取质数的方法:

def get_primes( n ):
    t = list(range(3,n,2))
    for i in range(len(t)):
        if t[i]:
            t[i+t[i]::t[i]] = [0] * len( t[i+t[i]::t[i]] )
    return [2] + [x for x in t if x]

fc1735

P = []
L = list(range(1000001))
for i in range(2, len(L)):
  if L[i] == i:
    P.append(i)
    L[i] = i - 1
  for p in P:
    if i * p >= len(L):
      break
    if i % p == 0:
      L[i*p] = L[i] * p
      break
    L[i*p] = L[i] * (p - 1)

L[1] = 0
print(sum(L))

基于线性筛的方法
https://github.com/devinizz/project_euler/blob/master/page02/72.py

debuggerzh

303963552391

Process returned 0 (0x0)   execution time : 0.064 s
Press any key to continue.
线性筛打表，欧拉函数递推（来自2#69题的方法）

#include<iostream>
#include<cmath>
using namespace std;

const int M = 1e6;
int ct = 0;
bool prime[M+10];
int factor[M+10];
int phi[M+10] = {0};

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) {factor[++ct] = i;  phi[i] = i-1;}
    for (int j = 1;j <= ct && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

void ini(){
  for (int i = 2;i <= sqrt(M);i++){
    if (prime[i]){
      for (int j = i;j*i <= M;j++)
        if (j % i == 0) phi[j*i] = phi[j] * i;
        else            phi[j*i] = phi[j] * (i-1);
    }
  }
}

int main(){
  unsigned long long ans = 0;
  euler_sieve();  ini();

  for (int d = 2;d <= M;d++)
    //cout << phi[d] << endl;
    ans += phi[d];

  cout << ans << endl;
  return 0;
}

永恒的蓝色梦想

C++ 20ms

#include<iostream>
#include<vector>
#include<cstring>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr unsigned int UPPER_BOUND = 1000000;
    static bool is_prime[UPPER_BOUND];
    static unsigned int phi[UPPER_BOUND];
    vector<unsigned int> primes;
    unsigned int i, k;
    unsigned long long result = 0;

    memset(is_prime, -1, UPPER_BOUND);
    is_prime[0] = is_prime[1] = 0;


    for (i = 2; i < UPPER_BOUND; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            result += phi[i] = i - 1;
        }

        for (unsigned int j : primes) {
            k = i * j;

            if (k >= UPPER_BOUND) {
                break;
            }

            is_prime[k] = false;

            if (!(i % j)) {
                result += phi[k] = phi[i] * j;
                break;
            }

            result += phi[k] = phi[i] * (j - 1);
        }
    }


    cout << result << endl;
    return 0;
}