Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Saringan Eratosthenes dalam C

Temukan semua bilangan prima hingga batas tertentu dengan menandai kelipatannya.

Buat array kandidat dari 0 sampai N dan keluarkan 0 serta 1. Untuk setiap prima p, tandai kelipatannya. Penandaan dapat dimulai dari p * p karena kelipatan yang lebih kecil sudah memiliki faktor prima yang lebih kecil.

Penandaan baru hanya perlu dimulai untuk p hingga akar N. Untuk batas besar, hindari overflow p * p, misalnya memakai p <= N / p untuk p positif. Buffer harus menyediakan posisi N.

Versi klasik membutuhkan memori O(N) dan waktu sekitar O(N log log N). Uji batas 0, 1, 2, dan nilai yang lebih besar; penyesuaian contoh mungkin diperlukan untuk batas baru.

Kode C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("Primes up to %d:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Buka di kompiler

Keluaran yang diharapkan

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.