欧拉计划 发表于 2015-11-5 16:49:00

题目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 发表于 2016-9-25 04:14:17

7295372


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 发表于 2016-10-16 14:09:36

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

愤怒的大头菇 发表于 2016-12-6 00:05:33

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


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

愤怒的大头菇 发表于 2016-12-6 00:07:12

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


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

fc1735 发表于 2019-12-19 11:13:34

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 发表于 2020-1-9 15:56:45

#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;
}


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


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

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

      }
    }
      printf("\n");
}

debuggerzh 发表于 2020-8-31 17:42:16

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;
int factor;
set<int> fac_n;

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

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

bool co_prime(int x,int y){//x < y
if (prime) return true;
if (prime && 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;
    while(x % t == 0) {s.insert(t); x /= t;}
    if (x == 1 || prime) break;
}
if (prime) 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;
}

永恒的蓝色梦想 发表于 2020-12-31 17:26:00

本帖最后由 永恒的蓝色梦想 于 2020-12-31 18:03 编辑

#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 发表于 2021-3-21 12:15:05

本帖最后由 guosl 于 2021-3-21 12:45 编辑

/*
答案：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;
}
页: [1]
查看完整版本: 题目73：在1/3和1/2之间有多少个最简真分数？