Primzahlen(Lua)

-- Eine leere Tabelle anlegen und von 2 bis arg[1] füllen
local tab = {}
for i = 2, arg[1] do table.insert(tab, i) end
-- Nun über alle Key-Value-Paare in tab iterieren
for k, v in pairs(tab) do
  --[[ Sobald der Wert erreicht ist, dessen Quadrat
  den Maximalwert übersteigt, sind wir fertig. Begründung:
  Angenommen wir wären mit v=tab[k] und v*v>arg[1] 
  noch nicht fertig, dann muss es Zahlen z,tab[k+1] geben,
  so dass tab[k+1]>v, z<=arg[1] und tab[k+1]*y=z. 
  Für y bieten sich folgende Möglichkeiten:
  1. y>=v, dann gilt aber tab[k+1]*y>arg[1], d.h. z>arg[1] -> Widerspruch
  2. y<v, dann gilt mod(z,y)=0 und damit wäre z bereits
  vor dem Erreichen von v ausgeschlossen worden q.e.d ]]--
  if v*v > tonumber(arg[1]) then break end
  -- sonst erneut über alle Key-Value-Paare von tab iterieren
  for ke, va in pairs(tab) do
   --[[ Natürlich sind nur die Werte interessant, die 
   größer sind als der gerade betrachtete (v aus der
   äußeren Schleife) (1. Bedingung), denn nur diese 
   Werte kommen überhaupt als Vielfache von v in 
   Betracht (2. Bedingung). Reihenfolge der Bedingungen 
   wegen Kurzschluss! ]]-- 
   if va > v and math.mod(va, v) == 0 then
    -- diese Vielfachen von v sollen alle aus tab entfernt werden
    table.remove(tab, ke)
   end
  end
end
 
-- die übriggebliebene Tabelle ausgeben, sie enthält nur noch Primzahlen
table.foreach(tab, print)