Calculate sum of GCD's of 1 to N numbers with N

Asked Jul 06 '16 at 18:55

Active Jul 06 '16 at 19:12

Viewed 70 times

I have a value N which varies from

1 <= N <= 10^6

Say:

N = 5

I want to calculate sum

where :

sum = gcd(1,5) + gcd(2,5) + gcd(3,5) + gcd(4,5) + gcd(5,5)

I achieved this by writing these two functions :

function calculateSum($N){
    $gcdSum = 0;
    for($i = 1; $i <= $N; $i++){
        $gcdSum += gcd($N,$i);
    }
    return $gcdSum;
}

function gcd($a, $b){
    if($b == 0) {
        return $a;
    }
    else {
        return gcd($b, $a % $b);
    }
}

I want to know what other better and faster ways of doing this exist and how to achieve them.

edited Jul 06 '16 at 19:12

Brendan Abel

35,343
14
88
118

asked Jul 06 '16 at 18:55

Ajay

http://codereview.stackexchange.com/ – j08691 Jul 06 '16 at 18:56
you can start from N to 1 and using memorization – CSK Jul 06 '16 at 18:58
@CSK Any example on how this memorization works. it would be great help. – Ajay Jul 06 '16 at 19:00
2

i guess you can find all divisors of N and then divide 1-N by divisors.... if mod == 0 mean GCD – CSK Jul 06 '16 at 19:10
http://stackoverflow.com/questions/33568231/sum-of-greatest-common-divisor-of-all-numbers-till-n-with-n – user007 Jul 06 '16 at 19:11

Calculate sum of GCD's of 1 to N numbers with N

0 Answers0