题目73：在1/3和1/2之间有多少个最简真分数？

欧拉计划

Counting fractions in a range

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 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,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

可以看出 1/3 和 1/2 之间共有 3 个分数。

在 d ≤ 12,000 的升序真分数列表中，1/3 和 1/2 之间有多少个分数？

jerryxjr1220

1. 7295372
   
2. [Finished in 9.6s]
   
3. 
   
4. lst = []
   
5. for i in range(3,12001):
   
6.         for j in range (int(i/3),int(i/2+1)):
   
7.                 if j/i < 0.5 and j/i > 1/3:
   
8.                         lst.append(j/i)
   
9. lst = set(lst)
   
10. print (len(lst))

复制代码

jerryxjr1220

这题如果用欧拉函数算会更快，不过暴力算法9.6s也还可以，就不搞复杂了。

愤怒的大头菇

jerryxjr1220 发表于 2016-9-25 04:14

题目不是要求j/i是最简真分数吗

愤怒的大头菇

jerryxjr1220 发表于 2016-9-25 04:14

你这个结果是对的，但过程有点看不懂

fc1735

1. from math import gcd
   
2. print(sum(map(lambda x: len(list(filter(lambda y: gcd(y, x) == 1,
   
3.                                         range(x // 3 + 1, (x + 1) // 2)))),
   
4.               range(1, 12001))))

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/73.py

guoquanli

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. 
   
5. // 断一个数是否是真分数，返回判断标志，同时返回该分数
   
6. bool IsProFrac(int a, int b){
   
7.     if(b%a == 0 ){
   
8.         if(a == 1){
   
9.             return true;
   
10.         }
    
11.         return false;
    
12.     }
    
13.     return true;
    
14. }
    
15. 
    
16. 
    
17. void  AllProFrac(int d, float array[100]){
    
18.     int n = 0;
    
19.     for(int i = 2; i<= d; i++){
    
20.         for(int j = 1;j<i;j++){
    
21.             if(IsProFrac(j,i)){
    
22.                 array[n]=((float)j)/i;
    
23.                 printf("[%d,%d]\n",j,i);
    
24.                 n++;
    
25.             }
    
26.         }
    
27.     }
    
28.     return;
    
29. }
    
30. 
    
31. 
    
32. void Print(float array[100]){
    
33.     for(int i = 0; i<100;i++){
    
34.         printf("%5.2f ",array[i]);
    
35.         if((i+1)%10 == 0){
    
36.             printf("\n");
    
37.         }
    
38.     }
    
39. }
    
40. 
    
41. void maini)
    
42.     float array[100]={0};
    
43.     AllProFrac(12,array);   
    
44.     Print(array);
    
45.     for(int i = 0; i<100; i++){
    
46.         if(array[i]<(float)1/2 && array[i] >(float)1/3){
    
47.             printf("%5.4f ",array[i]);
    
48. 
    
49.         }
    
50.     }
    
51.         printf("\n");
    
52. }

复制代码

debuggerzh

7295372

Process returned 0 (0x0)   execution time : 11.403 s
Press any key to continue.
比71题多了一些工作，找出上下界表达式，逐一判断互质

1. #include<iostream>
   
2. #include<set>
   
3. using namespace std;
   
4. 
   
5. const int M = 1e6;
   
6. const int RANGE = 12000;
   
7. int ct = 0;
   
8. bool prime[M];
   
9. int factor[M];
   
10. set<int> fac_n;
    
11. 
    
12. void euler_sieve(){
    
13.   prime[1] = false;
    
14.   for (int i = 2;i <= M;i++) prime[i] = true;
    
15. 
    
16.   for (int i = 2;i <= M;i++){
    
17.     if (prime[i]) factor[++ct] = i;
    
18.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
19.       prime[i*factor[j]] = false;
    
20.       if (i % factor[j] == 0) break;
    
21.     }
    
22.   }
    
23. }
    
24. 
    
25. bool co_prime(int x,int y){//x < y
    
26.   if (prime[y]) return true;
    
27.   if (prime[x] && y % x)  return true;
    
28.   if (y == x*2 + 1) return true;
    
29. 
    
30.   for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    
31.     if (y % *it == 0) return false;
    
32.   }
    
33.   return true;
    
34. }
    
35. 
    
36. void parse(int x,set<int> & s){//分解质因数
    
37.   for (int i = 1; ;i++){
    
38.     int t = factor[i];
    
39.     while(x % t == 0) {s.insert(t); x /= t;}
    
40.     if (x == 1 || prime[x]) break;
    
41.   }
    
42.   if (prime[x]) s.insert(x);
    
43. }
    
44. 
    
45. int main(){
    
46.   euler_sieve();
    
47.   int ans = 0;
    
48. 
    
49.   for (int d = 5;d <= RANGE;d++){
    
50.     int lb = d/3 + 1,ub = (d-1) / 2;
    
51.     //cout << d << " " << lb << " " << ub << endl;
    
52.     for (int n = lb;n <= ub;n++){
    
53.       fac_n.clear();
    
54.       parse(n,fac_n);
    
55.       if (co_prime(n,d))  ans++;
    
56.     }
    
57.   }
    
58.   cout << ans << endl;
    
59. }
    

复制代码

永恒的蓝色梦想

1. #include<iostream>
   
2. 
   
3. 
   
4. 
   
5. bool judge(int a, int b) {
   
6.     int c;
   
7. 
   
8.     while (b) {
   
9.         c = a % b;
   
10.         a = b;
    
11.         b = c;
    
12.     }
    
13. 
    
14.     return a == 1;
    
15. }
    
16. 
    
17. 
    
18. 
    
19. int main {
    
20.     using namespace std;
    
21. 
    
22.     int deno, nume, max, count = 0;
    
23. 
    
24. 
    
25.     for (deno = 4; deno <= 12000; deno++) {
    
26.         max = deno >> 1;
    
27. 
    
28.         if (deno & 1) {
    
29.             max++;
    
30.         }
    
31. 
    
32.         for (nume = deno / 3 + 1; nume <= max; nume++) {
    
33.             count += judge(nume, deno);
    
34.         }
    
35.     }
    
36. 
    
37. 
    
38.     cout << count << endl;
    
39.     return 0;
    
40. }

复制代码

guosl

1. /*
   
2. 答案：7295372
   
3. 耗时：0.812547秒（单核）
   
4.       0.135768（8核）
   
5. */
   
6. #include <iostream>
   
7. #include<algorithm>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. int gcd(int a, int b)
    
12. {
    
13.   if (b == 0)
    
14.     return a;
    
15.   int c = a % b;
    
16.   while (c != 0)
    
17.   {
    
18.     a = b;
    
19.     b = c;
    
20.     c = a%b;
    
21.   }
    
22.   return b;
    
23. }
    
24. 
    
25. int main(void)
    
26. {
    
27.   double t = omp_get_wtime();
    
28.   int nCount = 0;
    
29. #pragma omp parallel for reduction(+:nCount) schedule(guided,4)
    
30.   for (int i = 1; i < 12000; ++i)
    
31.   {
    
32.     for (int j = 2 * i + 1; j < min(3 * i, 12001); ++j)
    
33.     {
    
34.       if (gcd(i, j) == 1)
    
35.         ++nCount;
    
36.     }
    
37.   }
    
38.   t = omp_get_wtime() - t;
    
39.   cout << nCount << endl << t << endl;
    
40.   return 0;
    
41. }
    

复制代码