如何在不使用标志变量或函数的情况下在 C++ 中查找范围内的素数？

Question

在我的教科书中，这个问题的算法和流程图使用标志variables.So我试了一下没有使用标志变量并得到了解决方案（下面给出）。但是它在C++中的实现非常令人费解。我们还没有正式学习 goto 语句。所以我怀疑它是否可以在不使用函数、goto 语句和标志变量而仅使用循环和条件语句的情况下在 C++ 中实现？

Answer 1

这是我对上述想法的实现，仅使用 for 循环和 if 语句对 j 进行了优化：

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    int l, r;
    bool good; // stores whether a certain i will be prime
    cin >> l >> r;
    for(int i = max(l, 2); i <= r; i ++) // 2 is the first prime number so we can just always start from it if l < 2
    {
        good = true; // we first assume i is prime
        for(int j = 2; j <= sqrt(i); j ++) // we only need to go to sqrt(i) because every factor of i that is <= sqrt(i) matches another factor that is >= sqrt(i). For example, the number 24 has factors: 1, 2, 3, 4, 6, 8, 12, 24, and the 4 factors on the left match the 4 on the right, and all 4 left factors are <= sqrt(24).
        {
            if(i % j == 0)
            {
                good = false; // if i is divisible by j, we know it is not prime and can just leave this loop
                break; // leave j loop
            }
        }
        if(good == true)
            cout << i << "\n";
    }
}

另一种可能的优化是保留一个以前素数的数组，因此您只需要尝试素数因子，但这需要从第一个素数而不是从 L 开始。

编辑：对不起，我刚刚意识到“good”是一个标志变量，但我不确定如果没有它，或者通过使用 goto 语句，或者尤其不是直接的方式是否可以解决问题去做。

编辑（再次）：找到了一种无需标志变量的方法：

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    int l, r;
    cin >> l >> r;
    for(int i = max(l, 2); i <= r; i ++) // 2 is the first prime number so we can just always start from it if l < 2
    {
        //good = true; // we first assume i is prime
        for(int j = 2; j <= sqrt(i); j ++) // we only need to go to sqrt(i) because every factor of i that is <= sqrt(i) matches another factor that is >= sqrt(i). For example, the number 24 has factors: 1, 2, 3, 4, 6, 8, 12, 24, and the 4 factors on the left match the 4 on the right.
        {
            if(i % j == 0)
            {
                i ++; // if i is divisible by j, we can increment i
                j = 1; // and also reset j to 1 (it will be 2 on the next run of the loop
                if(i > r) return 0;
            }
        }
        cout << i << "\n"; // if the code did not reset, it means that i was not divisible by any j and is therefore prime
    }
}

如何在不使用标志变量或函数的情况下在 C++ 中查找范围内的素数？

How to find prime numbers within a range in C++ without using flag variables or functions?

c++

primes

loops

conditional-statements