Вы когда-нибудь задумывались, как эффективно генерировать простые числа? Не смотрите дальше! В этой статье мы рассмотрим мощный алгоритм «Решето Эратосфена», который обеспечивает элегантное решение этой проблемы. Независимо от того, являетесь ли вы новичком или опытным программистом, это руководство предоставит вам множество методов реализации этого алгоритма на разных языках программирования.

Метод 1: реализация на Python
Начнем с реализации на Python. Вот псевдокод алгоритма Решета Эратосфена:

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n  0.5) + 1):
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False
    primes = []
    for i in range(2, n + 1):
        if sieve[i]:
            primes.append(i)
    return primes
n = 100
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

Метод 2: реализация на Java
Если вы предпочитаете Java, вот реализация, использующая массив для хранения сита:

import java.util.ArrayList;
import java.util.List;
public class SieveOfEratosthenes {
    public static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] sieve = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            sieve[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (sieve[i]) {
                for (int j = i * i; j <= n; j += i) {
                    sieve[j] = false;
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (sieve[i]) {
                primes.add(i);
            }
        }
        return primes;
    }
    public static void main(String[] args) {
        int n = 100;
        List<Integer> primeNumbers = sieveOfEratosthenes(n);
        System.out.println(primeNumbers);
    }
}

Метод 3: реализация на C++
Если вы энтузиаст C++, вот реализация, использующая вектор для хранения решета:

#include <iostream>
#include <vector>
using namespace std;
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> sieve(n + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i) {
                sieve[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}
int main() {
    int n = 100;
    vector<int> primeNumbers = sieveOfEratosthenes(n);
    for (int prime : primeNumbers) {
        cout << prime << " ";
    }
    cout << endl;
    return 0;
}

Решето Эратосфена — замечательный алгоритм генерации простых чисел. В этой статье мы рассмотрели три различные реализации на Python, Java и C++. Используя этот алгоритм, вы можете эффективно генерировать простые числа для различных приложений. Так зачем ждать? Погрузитесь в мир простых чисел и откройте новые возможности с Решетом Эратосфена!