用c++2010写出判断素数的代码

在 C++2010 中，我们可以使用传统的试除法算法来判断一个数是否是素数。下面是一个简单的函数示例：

#include <iostream>
using namespace std;

// 判断一个数是否为素数的辅助函数
bool isPrime(int num) {
    if (num <= 1)
        return false;
    if (num == 2)
        return true;
    if (num % 2 == 0) // 数字是偶数，除了2之外的偶数都不是素数
        return false;
    
    for (int i = 3; i * i <= num; i += 2) // 只需要检查奇数因子
        if (num % i == 0)
            return false;
    
    return true;
}

int main() {
    int num;
    cout << "请输入一个整数: ";
    cin >> num;
    if (isPrime(num))
        cout << num << " 是素数." << endl;
    else
        cout << num << " 不是素数." << endl;
    return 0;
}

相关问题

提供判断素数的2种算法,要求写出算法伪代码和C/C++描述

当然，我可以介绍两种常见的判断素数的算法，一种是简单的暴力判断法，另一种是著名的埃拉托斯特尼筛法。

**1. 暴力判断法 (试除法)**

这个方法适用于较小的数字，其基本思想是从2开始，一直测试到数字本身是否能整除它。如果能整除，那么就不是素数，否则是素数。

**暴力判断法伪代码:**

function isPrime(n):
    if n <= 1:
        return false
    for i from 2 to sqrt(n):
        if n % i == 0:
            return false
    return true

**C/C++ 描述:**

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;
}

**2. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)**

这是一种更高效的筛选大范围素数的方法，通过遍历从2开始的所有数，每次去除所有该数倍数的数，直到达到最大值。

**埃拉托斯特尼筛法伪代码:**

function sieveOfEratosthenes(n):
    primes[0] = primes[1] = false
    for p from 2 to sqrt(n):
        if primes[p]:
            for i from p^2 to n with step p:
                primes[i] = false
    primes[2..sqrt(n)] = true
    result = [p for p in range(2, n+1) if primes[p]]

**C/C++ 描述:**

void sieveOfEratosthenes(int n, vector<bool>& primes) {
    primes.resize(n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (primes[p]) {
            for (int i = p * p; i <= n; i += p)
                primes[i] = false;
        }
    }
    for (int p = 2; p < n; ++p) {
        if (primes[p])
            result.push_back(p);
    }
}

提供判断素数的2种算法，要求写出算法伪代码 和C/C++描述

当然，这里有两种常见的判断素数的算法：

**1. 菲波那契筛法 (也称为埃拉托斯特尼筛法)**

这是一种用于找出一定范围内所有质数的传统算法。以下是简单的伪代码：

function sieveOfEratosthenes(n):
    primes = [True] * (n + 1)  # 初始化数组为全真
    primes[0], primes[1] = False, False  # 0和1不是质数

    for i in range(2, int(sqrt(n)) + 1):  # 只需检查到√n
        if primes[i]:  # 如果i是质数
            for j in range(i*i, n+1, i):  # 将其倍数标记为非质数
                primes[j] = False

    return [i for i in range(n + 1) if primes[i]]  # 返回所有质数

**2. 直接试除法**

这种方法简单直观，通过循环检查每个数是否能整除小于它的数，如果都不能，则该数为质数。以下是伪代码：

function isPrime(number):
    if number < 2:
        return false

    for i from 2 to sqrt(number):
        if number % i == 0:  # 如果找到因子
            return false

    return true  # 没有找到因子，所以是质数

function findPrimes(n):
    primes = []
    for i from 2 to n:
        if isPrime(i):
            primes.append(i)
    return primes