c++ 判断素数，给出函数实现

以下是判断素数的函数实现（C语言）：

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (isPrime(n)) {
        printf("%d是素数\n", n);
    } else {
        printf("%d不是素数\n", n);
    }
    return 0;
}

该函数的实现思路是：若n小于等于1，则不是素数；否则，从2开始遍历到sqrt(n)，若存在一个因子i满足n%i==0，则n不是素数，否则n是素数。

相关问题

c++ 判断素数，给出函数实现，复杂度尽量小

一个数除了1和它本身没有其他因数，那么这个数就是素数。因此，我们可以从2开始，一直到这个数的平方根，判断是否能整除，如果能整除就不是素数，否则就是素数。

以下是一个实现：

int isPrime(int n) {
    if (n <= 1) {
        return 0;
    }
    int i;
    for (i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

这个函数接受一个整数作为参数，返回一个布尔值，表示这个数是否是素数。如果是素数，返回1，否则返回0。如果输入参数小于等于1，则返回0。

这个函数的时间复杂度是O(sqrt(n))，因为我们只需要从2到平方根n的范围内遍历一次即可判断是否是素数。

c++判断素数用什么函数

在C++中，标准库并没有直接提供用于判断素数的函数。但是，你可以自定义一个函数来实现这一功能，如之前提到的`isPrime`函数。如果你想用标准库提供的函数，可能会涉及到一些数学库，例如`<bitset>`或第三方库。

如果你想要简单快速地判断素数，可以考虑使用`std::numeric_limits`下的`sqrt()`函数配合取模运算，但这通常不是最优解，因为它会涉及大量的浮点计算。更常见的做法还是使用迭代器从2到`std::sqrt(num)`进行检查，忽略偶数并跳过3的倍数。

以下是使用迭代器和取模操作的一个基本版本：

#include <iostream>
#include <cmath>

bool isPrime(int num) {
    if (num <= 1)
        return false;
    if (num == 2)
        return true;

    int sqrt_num = static_cast<int>(std::sqrt(num));
    for (int i = 3; i <= sqrt_num; i += 2) {  // 只需检查奇数
        if (num % i == 0)
            return false;
    }

    return true;
}

int main() {
    int number;
    std::cout << "Enter a number: ";
    std::cin >> number;
    std::cout << (isPrime(number) ? "The number is prime." : "The number is not prime.") << std::endl;
    return 0;
}

如果你需要更高性能的算法，可以使用如Miller-Rabin素数测试等专门算法，但这已经超出了基础的C++知识范围。