可以被1到20的所有数字整除的最小数字？

Question

我做了这个问题[ Project Euler problem 5 ],但编程方式很糟糕,请参阅c ++中的代码,

#include<iostream>
using namespace std;
// to find lowest divisble number till 20

int main()
{
int num = 20, flag = 0;

while(flag == 0)
{
    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)       

    {
        flag =  1;
        cout<< " lowest divisible number upto 20 is  "<< num<<endl;
    }

    num++;
}

}

我是用c ++解决这个问题并陷入循环,如何解决这一步......

• 考虑num = 20并将其除以1到20之间的数字
• 检查所有余数是否为零,
• 如果是,退出并显示输出数量
• 或者是num ++

我不知道如何使用控制结构,这一步也是如此

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) `

如何以正确的方式编码？

这个问题的答案是:

abhilash@abhilash:~$ ./a.out 
 lowest divisible number upto 20 is  232792560

Answer 1

可被两个数字整除的最小数字是这两个数字的最小公倍数.实际上,由一组N个数字x1..xN整除的最小数字是这些数字的LCM.很容易计算两个数字的LCM(参见维基百科文章),你可以通过利用以下事实扩展到N个数字

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

注意:注意溢出.

代码(在Python中):

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))

Answer 2

将所有从1到20的整数计入其主要因子分解中.例如,因子18为18 = 3 ^ 2*2.现在,对于p在1到20范围内的某个整数的素数因子分解中出现的每个素数,找到它在所有那些主要因子分解中具有的最大指数.例如,素数3将具有指数,2因为它在18的因式分解中显示为3 ^ 2,并且如果它出现在指数为3(即3 ^ 3)的任何素数因子分解中,则该数字必须至少为大到3 ^ 3 = 27,它在1到20的范围之外.现在用它们相应的指数收集所有这些素数,你得到了答案.

因此,举例来说,让我们找到可以被1到4的所有数字整除的最小数字.

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

出现的素数是2和3.我们注意到2is 2的最大指数和最大指数3is 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

Answer 3

使用数论可以更快地解决问题.其他答案包含指示如何执行此操作.这个答案只是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)
  { ...}
}

风格不是很好,但我认为这就是你要找的东西.