Lcm sum sum

Computer Science Level 4

$\large\sum _{ j=1 }^{ { 10 }^{ 3 } }{ \sum _{ i=1 }^{ { 10 }^{ 4 } }{ \text{lcm}(i,j) } } = \ ?$

The answer is 18286263868098.

2 solutions

Miloje Đukanović
Oct 10, 2015

#include<iostream>
using namespace std;

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

int lcm ( int a, int b)
{
    return a*b/gcd(a,b);
}

int main(){
int i,j;
long long int sum=0;
for(j=1;j<=1000;j++){
    for(i=1;i<=10000;i++){
        sum+=lcm(i,j);
    }
}
cout<<sum;

}

Bill Bell
Nov 9, 2015

Never re-invent the wheel. The author of this module is a much better programmer than most of us could hope to be.

from gmpy2 import lcm

total=0
for j in range(1,1+10**3):
    for i in range(1,1+10**4):
        total+=lcm(i,j)

print total

Lcm sum sum

The answer is 18286263868098.

2 solutions

0 pending reports