Alikvotní součet a klasifikace

O(n log n)

Alikvotní součet σ(m) je součet všech vlastních dělitelů m (tj. dělitelů bez m samotného). Toto síto počítá σ přičítáním d ke každému vlastnímu násobku m > d pro d od 1 do n−1. Každé číslo je pak klasifikováno: dokonalé pokud σ=m (nejmenší je 6), nadbytečné pokud σ>m (nejmenší je 12), nebo nedostatkové pokud σ<m (většina prvočísel). Dokonalá čísla jsou pozoruhodně vzácná — pod milion jsou známa pouze čtyři. Síto běží v čase O(n log n).

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

Jak to funguje

  1. Inicializace alikvotních součtů na 0 pro 2..n
  2. Pro každé d přičti d ke každému vlastnímu násobku
  3. Klasifikuj každé m jako dokonalé, nadbytečné nebo nedostatkové
  4. Výpis klasifikace

Pseudokód

1aliquotSum(n):                      # O(n log n)2  sigma[2..n] = 03  for d = 1 to n-1:4    for m = 2*d to n step d:5      sigma[m] += d                # d is a proper divisor of m6  for m = 2 to n:7    if sigma[m] == m: perfect8    elif sigma[m] > m: abundant9    else: deficient