我如何使它更有效-考虑分数 n/d，其中 n 和 d 是正整数

Question

如何提高效率

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

If can be seen that there are 21 elements in this set.
Write a program to count the number of proper fractions for a given number d.


function GCD(a,b) {
    while(a != b){
        if(a > b)
                a -= b;
        else
                    b -= a;
    }
    return a;
}

function countProperFractions(d) {
count = 0;
        num = [];
        den = [];
    for( j = 1; j <= d; j++){
        for( n = 1; n < j; n++) {
                num.push(n);
                    den.push(j);
            }
        }
        for(i = 0; i < num.length; i++){
            if(GCD(num[i],den[i])==1)
                count+=1;
        }
    return count;
}

Answer 1

您可以使用 this 函数来获取与给定数 n 互质的正整数的个数。

某种前缀数组将帮助您更快地找到解决方案。

这是一个implementation.

我如何使它更有效-考虑分数 n/d，其中 n 和 d 是正整数

How do I make this more efficient- Consider the fraction, n/d, where n and d are positive integers

javascript

performance

fractions

data-structures