c++ - 随机生成质数

Question

我正在尝试随机生成一个素数，但它似乎不起作用，而是只是抛出一个普通数。

我试过使用 isPrime 函数，并更改我生成数字的位置

bool isPrime(int n) {
    int flag = 0;
    for (int i = 2; i < n / 2; ++i) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
        if (flag == 0) return true;
        else return false;
    }
}
void generatePublicKey() {

    int p = 0;
    int q = 0;

    while (!isPrime(p)) {
        srand(time(NULL));
        p = rand();
    }

    std::cout << p;

}

Answer 1

停止条件在n 时不起作用是4。至少需要改为<= .

for (int i = 2; i <= n / 2; ++i)

更好的是，我认为您要寻找的极限不是 ½n 而是 √n。我们应该循环到i <= sqrt(n) ，或者等价地:

for (int i = 2; i <= n / i; ++i)

---

flag检查应该在循环之外。当它在循环内时，它会触发阻止循环完成的第一次迭代。

bool isPrime(int n) {
    int flag = 0;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }
    if (flag == 0) return true;
    else return false;
}

任何时候你写 if (condition) return true; else return false;它可以简化为更短但等效的 return condition; .

bool isPrime(int n) {
    int flag = 0;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }
    return flag == 0;
}

如果你只返回false，你甚至可以去掉这个标志一旦找到除数。

bool isPrime(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

---

while (!isPrime(p)) {
    srand(time(NULL));
    p = rand();
}

您只想为随机数生成器播种一次。每次迭代都重新播种 PRNG 将使您一遍又一遍地获得相同的数字。移动 srand()调用循环。

把它改成do-while循环也很聪明。您要确保在调用 isPrime 之前生成一个随机数.

srand(time(NULL));
do {
    p = rand();
} while (!isPrime(p));

注意: 移动 srand() 会更好调用generatePublicKey()完全。理想情况下，它应该在 main() 的开头调用一次。 .