时间戳

首页 > 解决方案 > 仅当父循环的所有迭代都为真时，如何执行嵌套的 if 语句？

c++ - 仅当父循环的所有迭代都为真时，如何执行嵌套的 if 语句？

问题描述

我正在尝试Project Euler 的问题 5。我需要找到能被前 20 个自然数整除的最小整数。

我的想法是将smallest变量初始化为 2520（正如问题中给出的那样）并在 11 开始循环，然后除以smallest11 到 20 的数字。如果它可以被 i 的所有值整除，那么系统应该打印smallest. 否则，它应该增加smallest1。下面是我到目前为止的代码。

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int smallest = 2520;
    for(int i = 11; i<=20; i++){
        if(smallest%i==0){
            cout<<smallest;  //I want this statement to be executed only when the if statement is true for all values of i.
            break;
        } else {
                smallest++; //In case the if statement is false for any value of i, then do this.
            }
    }
    return 0;
}

运行我的代码给了我答案：2522

正确答案是：232792560

目前，如果即使是从 11 到 20 的单个值也可以除法smallest，那么它会中断循环并打印它，但我希望它只有在 11 到 20 的所有值都可以除法时才打印。

标签： c++

解决方案

由于您已经获得了有关代码的帮助，因此我将尝试研究您的算法。

试着回想你的数学课并记住素数分解（10 = 2*5、12 = 2*2*3 等）。然后回想一下，一个数字可以被一个数字整除当且仅当它可以被它分解成的所有素数整除（在它们的最高幂 - 如果一个数字可以被 2^2 和 3 整除，那么它可以被 12 整除）。

在这种情况下这意味着什么？不要循环遍历〜232000000个数字，而是尝试分解1-20并记录您看到的每个素数的最大功率。然后将所有这些相乘以获得您的答案。

例子。1-10 分解如下：

1   1
2   2
3   3
4   2^2
5   5
6   2*3
7   7
8   2^3
9   3^2
10  2*5

如您所见，这里的最高权力是：

2^3
3^2
5
7

如果我们将它们相乘，那么：2^3 * 3^2 * 5 * 7 = 2520这是您在问题中得到的示例答案。

分解接下来的 10 个数字，我们得到：2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560。

再去下一个 10 给我们：2^4 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 2,329,089,562,800- 循环那么高可能需要一段时间。

无论如何，它与您的代码没有太大关系，但是弄清楚如何编写这个素数分解解决方案可能是一个很好的挑战，而且我认为如果您正在处理 Project Euler 问题，您可能会喜欢看到替代方案方法。:)

推荐阅读