数组求n以内的所有素数

数组求n以内的所有素数是一个常见的算法练习，主要是找出小于或等于给定数值n的所有质数。质数是指只有1和自身两个正因数的自然数。以下是使用Python编写的一个简单算法示例：

def find_primes(n):
    primes = []
    for num in range(2, n+1):  # 从2开始，因为1不是质数
        is_prime = True
        for i in range(2, int(num**0.5) + 1):  # 只需检查到num的平方根，超过这个范围的因子必定有一个已经在范围内
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

# 使用示例
n = 50
prime_array = find_primes(n)
print(f"2到{n}之间的所有质数是: {prime_array}")

相关问题

C++数组求n以内的所有素数

在C++中，求解一定范围内（比如n以内）的所有素数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种经典算法，通过标记并删除合数来找到素数。下面是简单的步骤：

1. 创建一个布尔类型的数组`isPrime`，大小为`n+1`，默认所有元素初始化为true，因为开始认为从2到n的每一个数字都是素数。

2. 遍历从2开始，直到√n（向下取整），对于每个素数p：
- 如果`isPrime[p]`为true，则它是素数，将它的倍数（除了它自身）标记为非素数，即`isPrime[2*p..n] = false`。
- 因为只需要检查到√n，因为超过这个范围的因子都与较小的因子配对存在，例如4和6的因子分别是2和3。

3. 最后，遍历`isPrime`数组，找出所有值为true的位置，它们对应的索引就是n以内的素数。

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p=2; p*p<=n; ++p) {
        if (isPrime[p]) {
            for (int i=p*p; i<=n; i += p)
                isPrime[i] = false;
        }
    }

    // 输出素数
    for (int p=2; p<=n; ++p)
        if (isPrime[p])
            cout << p << " ";
}

int main() {
    int n = 50; // 想要查找的范围
    sieveOfEratosthenes(n);
    return 0;
}

运行上述代码，会打印出50以内的所有素数。

输入一个正整数n，求n以内的素数。输入一个正整数n，求n以内的素数。请使用数组用筛选法实现

以下是使用筛选法实现求n以内素数的代码：

def find_primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    primes = [i for i in range(n+1) if is_prime[i]]
    return primes

这个函数接受一个正整数n作为参数，返回一个列表，其中包含了所有小于等于n的素数。它使用了筛选法，首先初始化一个长度为n+1的布尔数组is_prime，其中is_prime[i]表示i是否为素数。然后从2开始遍历到n的平方根，如果当前数i是素数，则将i的倍数都标记为非素数。最后遍历一遍is_prime数组，将所有为True的下标加入到primes列表中，即为答案。