C++ 能被 1 到 20 的所有数整除的最小数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2127039/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Smallest number that is evenly divisible by all of the numbers from 1 to 20?
提问by Abhilash Muthuraj
I did this problem [Project Euler problem 5], but very bad manner of programming, see the code in c++,
我做了这个问题[ Project Euler question 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++;
}
}
i was solving this in c++ and stuck in a loop, how would one solve this step......
我正在用 C++ 解决这个问题并陷入循环，如何解决这一步......
- consider num = 20 and divide it by numbers from 1 to 20
- check whether all remainders are zero,
- if yes, quit and show output num
- or else num++
- 考虑 num = 20 并将其除以从 1 到 20 的数字
- 检查所有余数是否为零，
- 如果是，退出并显示输出编号
- 否则 num++
i din't know how to use control structures, so did this step
我不知道如何使用控制结构，所以这一步
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) `
how to code this in proper manner?
如何以正确的方式对此进行编码？
answer for this problem is:
这个问题的答案是：
abhilash@abhilash:~$ ./a.out
lowest divisible number upto 20 is 232792560
回答by MAK
The smallest number that is divisible by two numbers is the LCMof those two numbers. Actually, the smallest number divisible by a set of N numbers x1..xN is the LCM of those numbers. It is easy to compute the LCM of two numbers (see the wikipedia article), and you can extend to N numbers by exploiting the fact that
能被两个数整除的最小数是这两个数的LCM。实际上，可被一组 N 个数字 x1..xN 整除的最小数字是这些数字的 LCM。计算两个数字的 LCM 很容易（请参阅维基百科文章），并且您可以利用以下事实扩展到 N 个数字
LCM(x0,x1,x2) = LCM(x0,LCM(x1,x2))
Note: Beware of overflows.
注意：小心溢出。
Code (in Python):
代码（在 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))
回答by jason
Factor all the integers from 1 to 20 into their prime factorizations. For example, factor 18 as 18 = 3^2 * 2. Now, for each prime number pthat appears in the prime factorization of some integer in the range 1 to 20, find the maximum exponent that it has among all those prime factorizations. For example, the prime 3will have exponent 2because it appears in the factorization of 18 as 3^2 and if it appeared in any prime factorization with an exponent of 3 (i.e., 3^3), that number would have to be at least as large as 3^3 = 27 which it outside of the range 1 to 20. Now collect all of these primes with their corresponding exponent and you have the answer.
将 1 到 20 之间的所有整数分解为它们的质因数分解。例如，因子 18 为 18 = 3^2 * 2。现在，对于p出现在 1 到 20 范围内的某个整数的素数分解中的每个素数，找到它在所有这些素数分解中的最大指数。例如，素数3将有指数，2因为它在 18 的因式分解中出现为 3^2，如果它出现在指数为 3（即 3^3）的任何素数因式分解中，则该数字必须至少为大为 3^3 = 27，它在 1 到 20 的范围之外。现在收集所有这些质数及其相应的指数，你就有了答案。
So, as example, let's find the smallest number evenly divisible by all the numbers from 1 to 4.
因此，例如，让我们找到可以被 1 到 4 的所有数字整除的最小数字。
2 = 2^1
3 = 3^1
4 = 2^2
The primes that appear are 2and 3. We note that the maximum exponent of 2is 2and the maximum exponent of 3is 1. Thus, the smallest number that is evenly divisible by all the numbers from 1 to 4 is 2^2 * 3 = 12.
出现的素数是2和3。我们注意到2is2的最大指数和3is的最大指数1。因此，可以被 1 到 4 的所有数字整除的最小数字是 2^2 * 3 = 12。
Here's a relatively straightforward implementation.
这是一个相对简单的实现。
#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;
}
Sample output:
示例输出：
Enter an integer: 20
Answer: 232792560
回答by Pascal Cuoq
There is a faster way to answer the problem, using number theory. Other answers contain indications how to do this. This answer is only about a better way to write the ifcondition in your original code.
有一个更快的方法来回答这个问题，使用数论。其他答案包含如何执行此操作的指示。这个答案只是关于if在原始代码中编写条件的更好方法。
If you only want to replace the long condition, you can express it more nicely in a for loop:
如果只想替换长条件，可以在 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)
{ ... }
becomes:
变成：
{
int divisor;
for (divisor=2; divisor<=20; divisor++)
if (num%divisor != 0)
break;
if (divisor != 21)
{ ...}
}
The style is not great but I think this is what you were looking for.
风格不是很好，但我认为这就是你要找的。
回答by mcdowella
See http://en.wikipedia.org/wiki/Greatest_common_divisorGiven two numbers a and b you can compute gcd(a, b) and the smallest number divisible by both is a * b / gcd(a, b). The obvious thing then to do is to keep a sort of running total of this and add in the numbers you care about one by one: you have an answer so far A and you add in the next number X_i to consider by putting
请参阅http://en.wikipedia.org/wiki/Greatest_common_divisor给定两个数字 a 和 b，您可以计算 gcd(a, b) 并且可以被两者整除的最小数字是 a * b / gcd(a, b)。显而易见的事情是保持这种运行的总和，并一个一个地添加你关心的数字：到目前为止你有一个答案 A 并且你添加下一个数字 X_i 以通过放置来考虑
A' = A * X_i / (gcd(A, X_i))
A' = A * X_i / (gcd(A, X_i))
You can see that this actually works by considering what you get if you factorise everything and write them out as products of primes. This should pretty much allow you to work out the answer by hand.
您可以通过考虑将所有内容因式分解并将它们写为质数的乘积而得到的结果来看到这实际上是有效的。这应该几乎可以让您手动计算出答案。
回答by George
Hint:
暗示：
instead of incrementing num by 1 at each step you could increment it by 20 (will work alot faster). Of course there may be other improvements too, ill think about it later if i have time. Hope i helped you a little bit.
而不是在每一步将 num 增加 1 你可以将它增加 20 （会工作得更快）。当然也可能有其他改进，以后有时间再考虑。希望我对你有所帮助。
回答by John R. Strohm
The number in question is the least common multiple of the numbers 1 through 20.
所讨论的数字是数字 1 到 20 的最小公倍数。
Because I'm lazy, let ** represent exponentiation. Let kapow(x,y) represent the integer part of the log to the base x of y. (For example, kapow(2,8) = 3, kapow(2,9) = 3, kapow(3,9) = 2.
因为我很懒，所以让**代表幂。让 kapow(x,y) 表示以 y 为底的 x 对数的整数部分。（例如，kapow(2,8) = 3、kapow(2,9) = 3、kapow(3,9) = 2。
The primes less than or equal to 20 are 2, 3, 5, 7, 11, 13, and 17. The LCM is,
小于或等于 20 的质数是 2、3、5、7、11、13 和 17。 LCM 是，
Because sqrt(20) < 5, we know that kapow(i,20) for i >= 5 is 1. By inspection, the LCM is
因为 sqrt(20) < 5，我们知道 kapow(i,20) for i >= 5 是 1。通过检查，LCM 是
LCM = 2kapow(2,20) * 3kapow(3,20) * 5 * 7 * 11 * 13 * 17 * 19
LCM = 2 kapow(2,20) * 3kapow(3,20) * 5 * 7 * 11 * 13 * 17 * 19
which is
这是
LCM = 24 * 32 * 5 * 7 * 11 * 13 * 17 * 19
LCM = 2 4 * 32 * 5 * 7 * 11 * 13 * 17 * 19
or
或者
LCM = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19
LCM = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19
回答by vector_L
#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;
}
The vector is used for storing the factors of the smallest number.
该向量用于存储最小数的因数。
回答by Brian Ogden
Here is a C# version of @MAK's answer, there might be List reduce method in C#, I found something online but no quick examples so I just used a for loop in place of Python's reduce:
这是@MAK 答案的 C# 版本，C# 中可能有 List reduce 方法，我在网上找到了一些东西，但没有快速示例，所以我只是使用 for 循环代替 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;
}
回答by zengr
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()
回答by Indrajith Indraprastham
this is written in c
这是用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();
}
}
