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

Anita Shah

How do I make this more efficient

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



asds_asds

You can use this function to get the count of positive integers which are relatively prime to a given number n.

Some sort of prefix array will help you get to the solution faster.

Here is an implementation.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

How do I make this matching list code more efficient?

How do I make the selection function more efficient?

How do I make my pygame levels more efficient?

How do I make the following C structure more memory efficient?

How would I make this script more efficient?

How can I make this loop more efficient?

How can I make this more efficient in Android?

How would I make this more efficient? (python)

I am trying to make a Fraction Calculator in HTML Javascript, I need to simplify the fraction how can I do this?

How to make np.where more efficient with triangular matrices?

How do I make this R code to format integers with leading zero more succinct?

How do I make this function for concatenating Excel sheets from a single file more efficient?

How do I make a more efficient color changer? VB.net

How do I make my VBA code more efficient using For each loops for three different ranges?

How do I make this VBA code more efficient so it does not crash due to lack of memory?

How do I make takeLatest consider url, params, and method?

How do I make uniq only consider the first field?

How do I make efficient queries in Django?

How do i make efficient slots in an inventory?

How can I make a code more efficient and shorter?

How can I make this Python code more efficient

How can I make this C# code more efficient?

How can I make my pandas code more efficient?

How can I make my trie more efficient?

How can I make this PyTorch heatmap function faster and more efficient?

How can I make this search query more efficient?

How would I make this code more compact/efficient?

How can I make a recursive search for longest node more efficient?

How can I make this more efficient path finding?