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

7295372
[Finished in 9.6s]

lst = []
for i in range(3,12001):
        for j in range (int(i/3),int(i/2+1)):
                if j/i < 0.5 and j/i > 1/3:
                        lst.append(j/i)
lst = set(lst)
print (len(lst))

jerryxjr1220

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

愤怒的大头菇

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

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

愤怒的大头菇

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

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

fc1735

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

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

guoquanli

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 断一个数是否是真分数，返回判断标志，同时返回该分数
bool IsProFrac(int a, int b){
    if(b%a == 0 ){
        if(a == 1){
            return true;
        }
        return false;
    }
    return true;
}


void  AllProFrac(int d, float array[100]){
    int n = 0;
    for(int i = 2; i<= d; i++){
        for(int j = 1;j<i;j++){
            if(IsProFrac(j,i)){
                array[n]=((float)j)/i;
                printf("[%d,%d]\n",j,i);
                n++;
            }
        }
    }
    return;
}


void Print(float array[100]){
    for(int i = 0; i<100;i++){
        printf("%5.2f ",array[i]);
        if((i+1)%10 == 0){
            printf("\n"); 
        }
    }
}

void maini)
    float array[100]={0};
    AllProFrac(12,array);    
    Print(array);
    for(int i = 0; i<100; i++){
        if(array[i]<(float)1/2 && array[i] >(float)1/3){
            printf("%5.4f ",array[i]);

        } 
    }
        printf("\n");
}

debuggerzh

7295372

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

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

const int M = 1e6;
const int RANGE = 12000;
int ct = 0;
bool prime[M];
int factor[M];
set<int> fac_n;

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;
    for (int j = 1;j <= ct && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

bool co_prime(int x,int y){//x < y
  if (prime[y]) return true;
  if (prime[x] && y % x)  return true;
  if (y == x*2 + 1) return true;

  for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
    if (y % *it == 0) return false;
  }
  return true;
}

void parse(int x,set<int> & s){//分解质因数
  for (int i = 1; ;i++){
    int t = factor[i];
    while(x % t == 0) {s.insert(t); x /= t;}
    if (x == 1 || prime[x]) break;
  }
  if (prime[x]) s.insert(x);
}

int main(){
  euler_sieve();
  int ans = 0;

  for (int d = 5;d <= RANGE;d++){
    int lb = d/3 + 1,ub = (d-1) / 2;
    //cout << d << " " << lb << " " << ub << endl;
    for (int n = lb;n <= ub;n++){
      fac_n.clear();
      parse(n,fac_n);
      if (co_prime(n,d))  ans++;
    }
  }
  cout << ans << endl;
}

永恒的蓝色梦想

#include<iostream>



bool judge(int a, int b) {
    int c;

    while (b) {
        c = a % b;
        a = b;
        b = c;
    }

    return a == 1;
}



int main {
    using namespace std;

    int deno, nume, max, count = 0;


    for (deno = 4; deno <= 12000; deno++) {
        max = deno >> 1;

        if (deno & 1) {
            max++;
        }

        for (nume = deno / 3 + 1; nume <= max; nume++) {
            count += judge(nume, deno);
        }
    }


    cout << count << endl;
    return 0;
}

guosl

/*
答案：7295372
耗时：0.812547秒（单核）
      0.135768（8核）
*/
#include <iostream>
#include<algorithm>
#include <omp.h>
using namespace std;

int gcd(int a, int b)
{
  if (b == 0)
    return a;
  int c = a % b;
  while (c != 0)
  {
    a = b;
    b = c;
    c = a%b;
  }
  return b;
}

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
#pragma omp parallel for reduction(+:nCount) schedule(guided,4)
  for (int i = 1; i < 12000; ++i)
  {
    for (int j = 2 * i + 1; j < min(3 * i, 12001); ++j)
    {
      if (gcd(i, j) == 1)
        ++nCount;
    }
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}