Kleinste Zahl, die teilbar durch alle zahlen von 1 bis 20?

Es ist ein schneller Weg, um Antwort auf die problem, mit der Zahl der Theorie. Andere Antworten enthalten Hinweise, wie dies zu tun. Diese Antwort ist nur über eine bessere Art und Weise zu schreiben, die if Zustand in Ihrem ursprünglichen code.

Wenn Sie nur wollen, ersetzen Sie die lange Bedingung, Sie können es Ausdrücken, mehr schön in einer for-Schleife:

 if ((num%2) == 0 && (num%3) == 0 && (num%4) == 0    && (num%5) == 0 && (num%6) == 0 
&& (num%7) == 0 && (num%8) == 0 && (num%9) == 0 && (num%10) == 0 && (num%11) == 0 && (num%12) ==0   
&& (num%13) == 0 && (num%14) == 0 && (num%15) == 0 && (num%16) == 0 && (num%17) == 0 && (num%18)==0
&& (num%19) == 0    && (num%20) == 0)     
{ ... }

wird:

{
  int divisor; 
  for (divisor=2; divisor<=20; divisor++)
    if (num%divisor != 0)
      break;
  if (divisor != 21)
  { ...}
}

Stil ist nicht toll, aber ich denke, das ist, was Sie gesucht haben.

Faktor, der die zahlen von 1 bis 20 in Ihrer prime factorizations. Zum Beispiel, Faktor-18 von 18 = 3^2 * 2. Nun, für jede Primzahl p erscheint, die Primzahl-ZERLEGUNG von einigen Ganzzahl im Bereich von 1 bis 20, finden Sie den maximalen Exponenten, dass es unter all den prime factorizations. Zum Beispiel der prime 3 haben Exponenten 2 da erscheint es in der Faktorisierung von 18 3^2, und wenn es schien, in jeder Primzahl-ZERLEGUNG mit einem Exponenten von 3 (D. H., 3^3),, die Zahl müsste mindestens so groß ist wie 3^3 = 27, die es außerhalb des Bereich von 1 bis 20. Jetzt sammeln Sie alle diese Primzahlen mit Ihren entsprechenden exponent und haben Sie die Antwort.

So, als Beispiel, finden wir die kleinste Zahl teilbar durch alle zahlen von 1 bis 4.

2 = 2^1
3 = 3^1
4 = 2^2

Die Primzahlen, die angezeigt werden 2 und 3. Wir beachten, dass der maximale exponent von 2 ist 2 und der maximale exponent von 3 ist 1. Also die kleinste Zahl, die teilbar durch alle zahlen von 1 bis 4 ist 2^2 * 3 = 12.

Hier ist eine relativ einfache Umsetzung.

#include <iostream>
#include <vector>

std::vector<int> GetPrimes(int);
std::vector<int> Factor(int, const std::vector<int> &);

int main() {
    int n;
    std::cout << "Enter an integer: ";
    std::cin >> n;
    std::vector<int> primes = GetPrimes(n);
    std::vector<int> exponents(primes.size(), 0);

    for(int i = 2; i <= n; i++) {
        std::vector<int> factors = Factor(i, primes);
        for(int i = 0; i < exponents.size(); i++) {
            if(factors[i] > exponents[i]) exponents[i] = factors[i];
        }
    }

    int p = 1;
    for(int i = 0; i < primes.size(); i++) {
            for(int j = 0; j < exponents[i]; j++) {
            p *= primes[i];
        }
    }

    std::cout << "Answer: " << p << std::endl;
}

std::vector<int> GetPrimes(int max) {
    bool *isPrime = new bool[max + 1];
    for(int i = 0; i <= max; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    int p = 2;
    while(p <= max) {
        if(isPrime[p]) {
            for(int j = 2; p * j <= max; j++) {
                isPrime[p * j] = false;
            }
        }
        p++;
    }

    std::vector<int> primes;

    for(int i = 0; i <= max; i++) {
        if(isPrime[i]) primes.push_back(i);
    }

    delete []isPrime;
    return primes;
}

std::vector<int> Factor(int n, const std::vector<int> &primes) {
    std::vector<int> exponents(primes.size(), 0);
    while(n > 1) {
        for(int i = 0; i < primes.size(); i++) {
        if(n % primes[i] == 0) { 
        exponents[i]++;
            n /= primes[i];
        break;
        }
            }
    }
    return exponents;
}

Beispiel-Ausgabe:

Enter an integer: 20
Answer: 232792560

Hinweis:

statt Inkrementierung num um 1 bei jedem Schritt, den Sie könnte es Inkrement von 20 (wird die Arbeit viel schneller). Natürlich kann es andere Verbesserungen, die auch krank denken Sie darüber später, wenn ich Zeit habe. Hoffe, ich half Ihnen ein wenig.

#include<vector>
using std::vector;
unsigned int Pow(unsigned int base, unsigned int index);

unsigned int minDiv(unsigned int n)
{
     vector<unsigned int> index(n,0);
     for(unsigned int i = 2; i <= n; ++i)
     {
         unsigned int test = i;
         for(unsigned int j = 2; j <= i; ++j)
         {
             unsigned int tempNum = 0;
             while( test%j == 0)
             {
                 test /= j;
                 tempNum++;
             }
             if(index[j-1] < tempNum)
                 index[j-1] = tempNum;
         }
     }
     unsigned int res =1;
     for(unsigned int i = 2; i <= n; ++i)
     {
         res *= Pow( i, index[i-1]);
     }
     return res;
 }

unsigned int Pow(unsigned int base, unsigned int index)
{
    if(base == 0)
        return 0;
    if(index == 0)
        return 1;
    unsigned int res = 1;
    while(index)
    {
        res *= base;
        index--;
    }
    return res;
}

Dieser Vektor wird verwendet für die Speicherung der Faktoren, die die kleinste Zahl.

Ruby Cheat:

require 'rational'

def lcmFinder(a = 1, b=2)
  if b <=20
    lcm = a.lcm b
    lcmFinder(lcm, b+1)
  end
  puts a
end


lcmFinder()

Hier ist ein C# - version von @MAK die Antwort, es könnte sein, die Liste zu reduzieren-Methode in C#, ich habe etwas gefunden online, aber keine schnelle Beispiele, so dass ich nur verwendet eine for-Schleife anstelle von Python reduce:

static void Main(string[] args)
    {
        const int min = 2;
        const int max = 20;
        var accum = min;

        for (var i = min; i <= max; i++)
        {
            accum = lcm(accum, i);
        }

        Console.WriteLine(accum);
        Console.ReadLine();
    }

    private static int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

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