能被1到20之间的所有数整除的最小数?

有一种更快的方法来回答这个问题,使用数论。其他答案包含如何做到这一点的指示。这个答案只是关于一个更好的方法来写 if 原始代码中的条件。

如果您只想替换long条件,可以在for循环中更好地表达它:

 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)     
{ ... }

变成:

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

款式不太好,但我想这就是你想要的。

可被两个数整除的最小数是 LCM 在这两个数字中。实际上,被一组N个数x1..xN整除的最小数是这些数的LCM。计算两个数字的LCM很容易(请参阅wikipedia文章),您可以利用以下事实扩展到N个数字:

LCM(x0,x1,x2) = LCM(x0,LCM(x1,x2))

注意:小心溢出。

def gcd(a,b):
    return gcd(b,a%b) if b else a

def lcm(a,b):
    return a/gcd(a,b)*b

print reduce(lcm,range(2,21))

将1到20之间的所有整数分解为素数分解。例如,因子18为18=3^2*2。现在,对于每个素数 p 3 将有指数 2

例如,让我们找到一个最小的数,它可以被1到4的所有数整除。

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

出现的素数是 2. 和 3. . 我们注意到 2. 是 2. 和的最大指数 是 1 . 因此,可以被从1到4的所有数字平均整除的最小数字是2^2*3=12。

这里是一个相对简单的实现。

#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;
}

样本输出:

Enter an integer: 20
Answer: 232792560

http://en.wikipedia.org/wiki/Greatest_common_divisor 给定两个数字a和b,你可以计算gcd(a,b),可被这两个数字整除的最小数字是a*b/gcd(a,b)。接下来要做的一件事就是保持一个这样的总数,把你关心的数字一一加进去:你有一个答案到目前为止A,你把下一个数字XII i加起来考虑。

A'=A*X_i/(gcd(A,X_i))

你可以看到,考虑到你得到的东西,如果你把所有的东西都分解,并把它们写成素数的乘积,这实际上是可行的。这几乎可以让你手工计算出答案。

提示:

所讨论的数字是数字1到20的最小公倍数。

因为我很懒,让**代表指数运算。让kapow(x,y)表示相对于y的基x的对数的整数部分(例如,卡波(2,8)=3,卡波(2,9)=3,卡波(3,9)=2。

小于或等于20的素数为2、3、5、7、11、13和17。LCM为,

因为sqrt(20)<5,我们知道kapow(i,20)表示i>=5为1。通过检查,LCM为

卡波(3,20) * 5 * 7 * 11 * 13 * 17 * 19

那是

4 * 3 2 * 5 * 7 * 11 * 13 * 17 * 19

或

19

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;
    }

var i=1,j=1;
    
for (i = 1; ; i++) {
    for (j = 1; j <= 20; j++) {
    
        if (i % j != 0) {
            break;
        }
        if (i % j == 0 && j == 20) {
            console.log('printval' + i)
            break;
        }
    }
}

这可以帮助你 http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization.php?number=232792560

232792560的素因子分解

2^4 3^2 5 7 11 13 17 19

require 'rational'

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


lcmFinder()

这是用c写的

#include<stdio.h>
#include<conio.h>
void main()
{

int a,b,flag=0;

for(a=1; ; a++)
{
    for(b=1; b<=20; b++)
    {
        if (a%b==0)
            {
                flag++;
            }

    }
    if (flag==20)
        {
            printf("The least num divisible by 1 to 20 is = %d",a);
            break;
        }
        flag=0;
}


getch();

}

#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;
}

向量用于存储最小数的因子。

这就是为什么编写这样的函数会让您受益匪浅:

long long getSmallestDivNum(long long n)
{
    long long ans = 1;
    if( n == 0)
    {
        return 0;
    }
    for (long long i = 1; i <= n; i++) 
        ans = (ans * i)/(__gcd(ans, i)); 
    return ans; 
}

给定最大值 n

让我们看一看1到20的集合。首先,它包含许多素数,即:

2
3
5
7 
11
13
17
19

所以,因为它必须除以19,你只能检查19的倍数,因为19是一个素数。然后,你检查它是否能被下面的那个除,等等。如果这个数能被所有的素数成功除,它就可以被1到20的数除。

float primenumbers[] = { 19, 17, 13, 11, 7, 5, 3, 2; };

float num = 20;

while (1)
{
   bool dividable = true;
   for (int i = 0; i < 8; i++)
   {
      if (num % primenumbers[i] != 0)
      {
         dividable = false;
         break;
      }
   }

   if (dividable) { break; }
   num += 1;
}

std::cout << "The smallest number dividable by 1 through 20 is " << num << std::endl;