Matematické Fórum

Ano, jde to. Výpočet faktoriálu je algoritmicky řešitelný problém a Pascal je Turing-kompletní jazyk -- takže se v Pascalu dá spočítat faktoriál.

Například takhle:

function factorial(n : integer) : longint;
begin
  factorial := 1;
  while n >= 1 do
    begin
      factorial := factorial * n;
      dec(n)
    end
end;

Ovšem dost rychle se ti stane, že se výsledek nevejde do jednoho longintu.

Skrývá se za otázkou nějaký hlubší problém, nebo jsem ti jenom vyřešil domácí úlohu z prográmka?

↑ Mr.Pinker:

Aha. To ale nevidím, k čemu tam potřebuješ faktoriál. Můžeš to zkusit nějak vysvětlit?

Jo takhle. To by určitě fungovalo, máš pravdu.

Ovšem -- jakmile dostaneš ne moc velké číslo -- třeba 1000 --, tak už se ti nevejde do žádného vestavěného datového typu a budeš muset použít takové věci jako dlouhá čísla, abys vůbec mohl (p - 1)! uložit v paměti.

Snažší a výpočetně méně náročný přístup je ten daleko přímější: Když máš na vstupu číslo p a chceš otestovat, jestli je prvočíslo, pak stačí projet všechna čísla od 2 do p - 1 a pokud některé z nich dělí p, pak p není prvočíslo.

Ostatně, nemusíš projíždět čísla až do p - 1 -- stačí poslední zkoušené číslo zvolit daleko nižší. Zkus se zamyslet jak.

Jestli a dělí b se dá zjistit pomocí operace „zbytek po dělení“, která se v Pascalu dělá operátorem mod. Například 5 mod 2 = 1, 6 mod 3 = 0.

↑ Mr.Pinker:stačí do

Ahoj, ta metoda s wilsonovou větou je sice teoreticky neefektivnější, ale i pro poměrně malá čísla je problém v obrovské hodnotě faktoriálu.
Pro zjišťování, zda je jedno číslo prvočíslem je prakticky nejlepší tedy vyzkoušet, zda je dělitelné dvojkou a všemi lichými čísly od 3 do odmocniny z testovaného čísla.
Pokud však chceš určit např. prvních 100 prvočísel nebo všechna prvočísla menší jak 100, pak je nejefektivnější tzv. eustachovo síto, viz Google :)

Ahoj, nepochopil jsem, jak funguje ten tvůj program, já bych to napsal takto:

program prvocislo;
var cislo,i : integer;
      prvocislo : boolean;
begin
   readln(cislo);
   prvocislo := true;
   if cislo <= 1 then {jednička, nula nebo záporné číslo není prvočíslo}
      prvocislo := false;
   if (cislo <> 2) AND (cislo mod 2 = 0) then {zadané číslo není dvojka a je sudé a proto není prvočíslo}
      prvocislo := false;
   else {zadané číslo je liché}
   begin
      i := 3;
      while i <= sqrt(cislo) do
      begin
         if cislo mod i = 0 then {zadané číslo je dělitelné číslem i a proto není prvočíslo}
         begin
            prvocislo := false;
            {ukonči cyklus while - něco jako v c++ break, není to však nutné}
         end
         i := i+2; {zvětší o dvojku potenciálního dělitele}
      end;
   end;
   if prvocislo = true then
      writeln('ANO');
   else
      writeln('NE');
   readln;
end.