用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>&amp; 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
登录后复制