eratosthene.cpp

Bài toán

In ra các số nguyên tố từ 1 đến n

Độ phức tạp

O(n log(logn))

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

bool nonpr[1230997];

int prime[1230997];

int nPrime;

void eratos(int n) {

    nonpr[0] = nonpr[1] = true;

    for (int i = 2; i <= n; i++)

        if (!nonpr[i])

            for (int j = i + i; j <= n; j += i)

                nonpr[j] = true;

    for (int i = 1; i <= n; i++)

        if (!nonpr[i]) prime[++nPrime] = i;

}

int main() {

    int i, n;

    scanf("%d", &n);

    eratos(n);

    for (i = 1; i <= nPrime; i++)

        printf("%d ", prime[i]);

}

Nhận xét