[Solved] Sum of LCM range from 1 to 10^9 [closed]

by 


// In pseudocode a very basic algorithm:
main
  for i: 1 to 1000000000
    if (TestValue(i))
      Output(i)

TestValue(i)
  for j: 1 to 99
    if j does not divide i evenly
      return false
  return true

Of course, this won’t be very performant. You might notice that if a number is evenly divisible by all numbers between 1 and 99, then it must be divisible by the set of prime factors in 1..99. For instance, in 1..19 the prime factors are: 2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, 19. If something is evenly divisible by all numbers 1..19 then it must be evenly divisible by 2*2*2*2*3*3*5*7*11*13*17*19 = 232792560. To find all the numbers between 1 and 1000000000 that are evenly divisible by 1..19, I would find all the numbers between 1 and 1000000000 that are evenly divisible by 232792560 instead.

2

solved Sum of LCM range from 1 to 10^9 [closed]