В чём ошибка? Подскажите, пожалуйста

[furt123]

В чём ошибка? Подскажите, пожалуйста

задача проста: нужно проверить простое или составное число по теореме Вильсона. до 13 работает. а потом нет.

var
  factorial: Uint64;
  n, z, i: integer;

begin
  write('n = '); readln(n);
  writeln('считаем факториал числа n-1');
  factorial := 1;
  for i := 2 to n - 1 do
    factorial := factorial * i;
  writeln('(n-1)! = ', factorial);
  begin
    writeln('проверяем:');
    z := factorial + 1;
    if z mod n = 0 then  writeln('остаток = 0 => n - простое число')
    else
    begin
      writeln('остаток ≠0 => n - составное число');
      
    end;
  end;
end.

 

[furt123]

пернёс z в тип Uint64, добился того, что работает до 19. судя по всему проблема в типах. может у вас есть мысли на счёт того как сделать, чтобы хотя бы до 43 работала.

 

[Vladimir_S]

пернёс z в тип Uint64, добился того, что работает до 19. судя по всему проблема в типах. может у вас есть мысли на счёт того как сделать, чтобы хотя бы до 43 работала.

Простыми средствами - никак. Мне в моем Free Pascal, благодаря использованию типа QWord (максимум - 18446744073709551615), тоже удалось продвинуться только до n=19. Дальше - всё, обруб.

var
  factorial: QWord;
  n, i: integer;

begin
 Repeat
  write('n (0 to exit) = ');
  readln(n);
  if n>0 then
   begin
    factorial := 1;
    for i := 2 to n - 1 do
     factorial := factorial * i;
    writeln('(n-1)! = ', factorial);
    writeln('testing:');
    if ((factorial+1) mod n)=0 then
     writeln('n is prime')
    else
     writeln('n is composite');
   end;
 Until n=0;
end.

 

[Vladimir_S]

Ну вот так, мало-мало встав на уши, удалось продвинуться до n=25:

var
 z,p,m:QWord;
 n,i:integer;

begin
 Repeat
  write('n (0 to exit) = ');
  readln(n);
  if n>0 then
   begin
    z:=1;
    i:=1;
    p:=1;
    repeat
     inc(i);
     z:=z*i;
     if (z mod 10)=0 then
      begin
       z:=z div 10;
       p:=p*10;
      end;
    until i=n-1;
    m:=((z mod n)*p) mod n;
    writeln('testing:');
    if m=n-1 then
     writeln('n is prime')
    else
     writeln('n is composite');
   end;
 Until n=0;
end.

На всякий случай: метод (только что мною изобретенный) основан на двух легко доказуемых положениях:
1. Если P+1 делится нацело без остатка на Q, то остаток от деления P на Q есть Q-1.
2. Пусть a,b,c,d,e - цифры. Пусть исследуемое число заканчивается k нулями, т.е., для примера, при k=4 запись числа имеет вид abcde0000. Оно, естественно, равно abcde*10000. Так вот, остаток от деления нашего числа на n можно вычислить так:
а) определяем остаток от деления abcde на n.
б) этот остаток умножаем на 10^k, т.е. в нашем примере на 10000.
в) находим остаток от деления полученного произведения на n - он и будет искомым ответом.

 

[furt123]

интересный методtehno032 , спасибо, Vladimir_S )