埃氏筛

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e2 + 6;
int input_arr[MAX_N];
int input(int *input_arr)
{
    int amount;
    cin >> amount;

    int input_num;
    for (int i = 0; i < amount; ++i)
    {
        cin >> input_num;
        input_arr[i] = input_num;
        cout << input_arr[i] << " ";		// debug
    }

    return amount;
}

const int MAX_PRIME = 1e5 + 6;
bool prime_by_sub[MAX_PRIME];
void era_prime(void)
{
    prime_by_sub[0] = prime_by_sub[1] = 1;
    for (int i = 2; i <= sqrt(MAX_PRIME); ++i)
    {
        for (int j = i * i; j <= MAX_PRIME; j += i)
        {
            prime_by_sub[j] = 1;
        }
    }
}

int main(void)
{
    int amount = input(input_arr);
    era_prime();

    for (int i = 0; i < amount; ++i)
    {
        if ( ! prime_by_sub[ input_arr[ i ] ] )
        {
            cout << input_arr[i] << " ";
        }
    }

    
    return 0;
}

埃氏筛

原文：https://www.cnblogs.com/ShyButHandsome/p/13168406.html