题目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））

1. from time import clock
   
2. start = clock()
   
3. 
   
4. def getPrime(n):
   
5.     primes = [True]*n
   
6.     primes[0], primes[1] = False, False
   
7.     for (i, prime) in enumerate(primes):
   
8.         if prime:
   
9.             for j in range(i*i,n,i):
   
10.                 primes[j] = False
    
11.     primelist = []
    
12.     for (k, trueprime) in enumerate(primes):
    
13.         if trueprime:
    
14.             primelist.append(k)
    
15.     return primelist
    
16. 
    
17. def philist(n):
    
18.     primelist = getPrime(n)
    
19.     PHI = [0]*(n+1)
    
20.     for eachprime in primelist:
    
21.         PHI[eachprime] = eachprime - 1
    
22.     for i in range(len(primelist)):
    
23.         p = primelist[i]
    
24.         for k in range(p*p,n+1,p):
    
25.                 PHI[k] = PHI[int(k/p)]*(p-1)
    
26.         for j in range(p*p,n+1,p*p):
    
27.             PHI[j] = PHI[int(j/p)]*p
    
28.     return PHI
    
29. plist = philist(1000000)
    
30. 
    
31. print(sum(plist))
    
32. 
    
33. end = clock()
    
34. 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 ...

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

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

复制代码

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

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

复制代码

fc1735

1. P = []
   
2. L = list(range(1000001))
   
3. for i in range(2, len(L)):
   
4.   if L[i] == i:
   
5.     P.append(i)
   
6.     L[i] = i - 1
   
7.   for p in P:
   
8.     if i * p >= len(L):
   
9.       break
   
10.     if i % p == 0:
    
11.       L[i*p] = L[i] * p
    
12.       break
    
13.     L[i*p] = L[i] * (p - 1)
    
14. 
    
15. L[1] = 0
    
16. 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题的方法）

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. 
   
5. const int M = 1e6;
   
6. int ct = 0;
   
7. bool prime[M+10];
   
8. int factor[M+10];
   
9. int phi[M+10] = {0};
   
10. 
    
11. void euler_sieve(){
    
12.   prime[1] = false;
    
13.   for (int i = 2;i <= M;i++) prime[i] = true;
    
14. 
    
15.   for (int i = 2;i <= M;i++){
    
16.     if (prime[i]) {factor[++ct] = i;  phi[i] = i-1;}
    
17.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
18.       prime[i*factor[j]] = false;
    
19.       if (i % factor[j] == 0) break;
    
20.     }
    
21.   }
    
22. }
    
23. 
    
24. void ini(){
    
25.   for (int i = 2;i <= sqrt(M);i++){
    
26.     if (prime[i]){
    
27.       for (int j = i;j*i <= M;j++)
    
28.         if (j % i == 0) phi[j*i] = phi[j] * i;
    
29.         else            phi[j*i] = phi[j] * (i-1);
    
30.     }
    
31.   }
    
32. }
    
33. 
    
34. int main(){
    
35.   unsigned long long ans = 0;
    
36.   euler_sieve();  ini();
    
37. 
    
38.   for (int d = 2;d <= M;d++)
    
39.     //cout << phi[d] << endl;
    
40.     ans += phi[d];
    
41. 
    
42.   cout << ans << endl;
    
43.   return 0;
    
44. }
    

复制代码

永恒的蓝色梦想

C++ 20ms

1. #include<iostream>
   
2. #include<vector>
   
3. #include<cstring>
   
4. 
   
5. 
   
6. 
   
7. int main() {
   
8.     using namespace std;
   
9.     ios::sync_with_stdio(false);
   
10. 
    
11.     constexpr unsigned int UPPER_BOUND = 1000000;
    
12.     static bool is_prime[UPPER_BOUND];
    
13.     static unsigned int phi[UPPER_BOUND];
    
14.     vector<unsigned int> primes;
    
15.     unsigned int i, k;
    
16.     unsigned long long result = 0;
    
17. 
    
18.     memset(is_prime, -1, UPPER_BOUND);
    
19.     is_prime[0] = is_prime[1] = 0;
    
20. 
    
21. 
    
22.     for (i = 2; i < UPPER_BOUND; i++) {
    
23.         if (is_prime[i]) {
    
24.             primes.push_back(i);
    
25.             result += phi[i] = i - 1;
    
26.         }
    
27. 
    
28.         for (unsigned int j : primes) {
    
29.             k = i * j;
    
30. 
    
31.             if (k >= UPPER_BOUND) {
    
32.                 break;
    
33.             }
    
34. 
    
35.             is_prime[k] = false;
    
36. 
    
37.             if (!(i % j)) {
    
38.                 result += phi[k] = phi[i] * j;
    
39.                 break;
    
40.             }
    
41. 
    
42.             result += phi[k] = phi[i] * (j - 1);
    
43.         }
    
44.     }
    
45. 
    
46. 
    
47.     cout << result << endl;
    
48.     return 0;
    
49. }

复制代码