Find the least common multiple in a range

[hanst99]

Nothing hard to do, but I thought it was entertaining while it lasted. Got this task from eulerproject.com - my solution is here ( http://pastebin.com/UZwR4P3z ), I'd really like to see how other people would attempt to do this.

(In case it's not clear - the task is to find the smallest number that is evenly divisible by all numbers from 1 to the specified range).

[ne555]

My compiler don't know what auto is.

I find the lcm using the gcd far more easy.

number gcd(number a, number b){
	if( b==0 ) return a;
	return gcd(b, a%b);
}
number lcm(number a, number b){
	return a*b / gcd(a,b);
}

result = 1;
for(int K=1; K<=n; ++K)
	result = lcm(K, result);

By the way, when calculating primes the dynamic method is awesome.

bool is_prime(number n);
bool is_dyn_prime(number n);
void generate( number limit );

std::vector<number> primes;

bool is_prime(number n){
	return binary_search(primes.begin(), primes.end(), n) or is_dyn_prime(n);
}

bool is_dyn_prime(number n){
	number root = sqrt(n) + 2; //I don't want issues with precision
	for(size_t K=0; K<primes.size() and primes[K]<root; ++K)
		if(n%primes[K] == 0) 
			return false;
	return true;
}

void generate( number limit ){
	if( limit>=2 )
		primes.push_back(2);
	for(number K=3; K<=limit; K+=2)
		if( is_dyn_prime(K) )
			primes.push_back(K);
}

[hamsterman]

#include <iostream>
#include <vector>

struct Eratosthenes{
   std::vector<unsigned> sieve;
   unsigned p;

   Eratosthenes() : p(2) {}

   unsigned operator * () const { return p; }

   void operator ++ (int){
      sieve.push_back( p );
      bool composite = true;
      while( composite ){
         p++;
         composite = false;
         for(int i = 0; i < sieve.size(); i++)
            if( p % sieve[i] == 0 ){
               composite = true;
               break;
            }
      }
   }
};

int main(){
   const int N = 10;
   int result = 1;
   for ( Eratosthenes P; *P <= N; P++ ){
      int n = N;
      while( n /= *P ) result *= *P;
   }
   std::cout << result;
   std::cin.get();
   return 0;
}

^{edit: sorry, I keep forgetting which ++ is which..
Oddly VC++ only gives a warning about that.}

[hanst99]

ne, what compiler are you using? it's a c++0x feature so maybe you just gotta tell your compiler to compile with 0x support.

[ne555]

@hamsterman: Great. :)
(but it does not compile)

@hanst99: okay, fixed.
however

int main()
{
	return getRangeLeastCommonMultiple(NUMBER);
}

¡¿how do you see the output?! It seems that echo $? makes % 256
(and using the return code it's just awful)

[hanst99]

Just replace that with any output method of your liking. Visual Studio shows the return code of the program when debugging, so I didn't bother to write actual output code.

[Mathhead200]

a%b What if a is negative?

[hanst99]

You can get a modulo of a negative number.