Submission

Score: 100

User: pinto

Problemset: จำนวนเฉพาะ (2560)

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-06 15:39:26

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

// Returns true if target is NOT in the list (i.e., not marked composite)
bool isPrime(int target, vector<int>& numbers) {
    return find(numbers.begin(), numbers.end(), target) == numbers.end();
}

// Mark all multiples of i (starting from i*i) as composite
void markComposites(int i, int n, vector<int>& arrayList) {
    for (int multiple = i * i; multiple < n; multiple += i) {
        arrayList.push_back(multiple);
    }
}

int main() {
    vector<int> arrayList;
    int n;
    cin >> n;

    for (int i = 2; i < n; i++) {
        if (isPrime(i, arrayList)) {
            cout << i << endl;         // i is prime, print it
            markComposites(i, n, arrayList); // mark its multiples
        }
    }

    return 0;
}