Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummath-number-theory

Count Primes

Problem (yeniden ifade)

Tamsayı n verildiğinde n’den küçük kaç asal olduğunu döndür.

Sezgi

Her adayı deneme bölmek O(n √n). Elek bileşikleri toplu işaretler: her asal p için katları p²’den başlayarak sil (daha küçük katlar daha küçük bir asalle zaten vuruldu).

Yaklaşımlar

Eratosthenes eleği

Doğrulanmadı

Zaman O(n log log n)Alan O(n)

Fikir. Boyu n boolean dizi, 0 ve 1 false. p 2’den p² < n iken, p hâlâ asalsa p², p²+p, … işaretle. Kalan true’ları say.

Yürüyüş. n = 10 → 2, 3, 5, 7 → 4. n ≤ 2 → 0.

Trade-off. Hızın bedeli doğrusal alan. Çarpmaya 2p’den değil p²’den başla. Cevap n’den küçük asallar, dizi uzunluğu n+1 değil n.

Çözüm

export function countPrimes(n: number): number {
  if (n <= 2) return 0;
  const prime = new Array<boolean>(n).fill(true);
  prime[0] = false;
  prime[1] = false;
  for (let p = 2; p * p < n; p++) {
    if (!prime[p]) continue;
    for (let m = p * p; m < n; m += p) prime[m] = false;
  }
  let c = 0;
  for (let i = 2; i < n; i++) if (prime[i]) c++;
  return c;
}

export function countPrimes(n: number): number {
  if (n <= 2) return 0;
  const prime = new Array<boolean>(n).fill(true);
  prime[0] = false;
  prime[1] = false;
  for (let p = 2; p * p < n; p++) {
    if (!prime[p]) continue;
    for (let m = p * p; m < n; m += p) prime[m] = false;
  }
  let c = 0;
  for (let i = 2; i < n; i++) if (prime[i]) c++;
  return c;
}

Şablon bağlantısı

Math & Number Theory’nin sieve şekli: boolean dizi, p*p’den sil. “n’den küçük” off-by-one’ı klasik tuzak.

Yansıma

0 ve 1 asal değil. p*p’ye kadar her asalın katlarını çiz. Cevap çizilmeyenlerin sayısı.
Çizime p*p’den başla. Daha küçük katları önceki asallar çizmiştir.
n ≤ 2 cevap 0. n = 3 cevap 1. p*p taşabilir.