Síto bezčtvercových čísel

O(n log log n)

Bezčtvercové číslo nemá ve svém rozkladu žádný opakující se prvočíselný faktor. Toto síto nejprve nalezne prvočísla do √n Eratosthenovým sítem, poté pro každé prvočíslo p označí každý násobek p² jako ne-bezčtvercový. Čísla, která přežijí všechna taková označení, jsou bezčtvercová (zobrazena zeleně); ostatní jsou hnědá. Hustota bezčtvercových čísel je 6/π² ≈ 0,608, takže přibližně 60,8 % celých čísel je bezčtvercových. Möbiova funkce μ(n) je nula přesně na ne-bezčtvercových číslech.

Čísla
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nalezení prvočísel do √n základním sítem
  2. Pro každé prvočíslo p označ násobky p² jako ne-bezčtvercové
  3. Odhal neoznačená čísla jako bezčtvercová
  4. Výpis počtu bezčtvercových čísel

Pseudokód

1squarefreeSieve(n):                 # O(n log log n)2  isSquareFree[2..n] = true3  primes = eratosthenes(floor(sqrt(n)))4  for p in primes:5    for m = p*p to n step p*p:6      isSquareFree[m] = false      # p^2 divides m7  return isSquareFree