Простое число, Небольшой вопросик ;-) Опции

[Legolas]

Всем привет
Вот насчет задачи:

Дано натуральное число п. Является ли оно простым?

а вот решение >>>

Код

program prost; {Џа®ўҐаЄ  зЁб«  ­  Їа®бв®вг (*Їа®б⮥ зЁб«®*)}
Uses CRT;
Var  n,s: longint;
 Function  Simple(n:longint):boolean;
  Var i:longint;simp : boolean   { simp=false, Ґб«Ё ўбваҐвЁ«бп ¤Ґ«ЁвҐ«м зЁб«  n};
  begin
   if n=2 then Simple:=false
   else if n mod 2 = 0 then Simple:=false
   else begin
   simp:=true;
{Здесь начало выделения;-)}
[B]i:=3;
   while (i<=trunc(sqrt(n))) and  simp do
      if n mod i =0 then simp:=false else i:=i+2;
      if simp then Simple:=true else Simple:=false
   end [/B]
{Здесь конец выделения;-)}
  end;
{Ћб­®ў­ п з бвм Їа®Ја л}
BEGIN  clrscr; textcolor(lightgreen);
write(' ‚ўҐ¤ЁвҐ зЁб«® ¤«п Їа®ўҐаЄЁ ­  Їа®бв®вг> ');
readln(n);
if Simple(n) then writeln(' Yes') else writeln(' No');
readln;
END.

Хотелось бы подробно узнать за что отвечает выделенная часть и как она работает, уже неделю не могу разобрать...
P.S. Задачу не сам делал
Всем заранее спасибо.

Сообщение отредактировано: Legolas - 23.05.2005 6:17

[klem4]

вот можно еще так, я думаю :

 i:=2;flag:=true;
  while(i<=9)and(flag) do
   if (n<>i)and(n mod i = 0) then
     flag:=false
   else
    inc(i);

  if not(flag) then writeln('Simple')
   else writeln('No');

хотя можно еще меньше цикл сделать, объявить массив

a[4] = (2,3,5,7) и в цикле

... if (n<>a[i])and(n mod a[i] = 0) then
     flag:=false;

Сообщение отредактировано: klem4 - 23.05.2005 7:44

[hiv]

Это выделение лучше переписать вот так:

i:=3;
while (i<=trunc(sqrt(n))) and  simp do 
begin
  simp:=(n mod i <>0);
  if simp then i:=i+2;
end;
Simple:=simp;

А если не понятно как работает данный алгоритм, задавай конкретные вопросы.

[klem4]

может у меня с просони мозг совсем не работает, тогда извеняйте ;) но это :

uses crt;
var i,n:integer;
    simp,simple:boolean;

begin
   readln(n);
   i:=3;simp:=true;
   while (i<=trunc(sqrt(n))) and  simp do
   begin
      simp:=(n mod i <>0);
     if simp then i:=i+2;
   end;
  Simple:=simp;
  writeln(simple);
end.

всегда true.

вру, не всегда, при n=9 и n=12 - false но это ведь не правда)).
hiv , поясни алгоритм

Сообщение отредактировано: klem4 - 23.05.2005 9:05

[Бродяжник]

Выделенная часть напрямую связана со всей программой. Поэтому разбираем сначала.
Вначале проверяем, делится ли заданное число на 2. Четные числа заведомо не простые. Если же число нечетное, переходим к выделенной части. В этом цикле мы перебираем все возможные нечетные делители, начиная с 3 и заканчивая квадратным корнем из заданного числа. Поскольку для нечетного числа возможны только нечетные делители, то и шаг по i идет через двойку. А почему заканчиваем trunc(sqrt(n)), тоже понятно. Потому что корень из числа это максимальный возможный делитель.
А вот что мне не нравится, так это строка в самом начале:

if n=2 then Simple:=false

Господа маститые, прокомментируйте pls. Неужели я забыл школьную арифметику?

[volvo]

Legolas
Опять изобретаем велосипед ... Чем Этот способ не устраивает?

[hiv]

Неужели я забыл школьную арифметику?

Ты абсолютно прав - это я не доглядел...

всегда true.

Это был кусок кода - а вот весь:

Function  Simple(n:longint):boolean;
var i :integer;
    simp :boolean;
begin
  if n=2 then Simple:=true
  else
    if n mod 2 = 0 then Simple:=false
    else
    begin
      i:=3;simp:=true;
      while (i<=trunc(sqrt(n))) and  simp do
      begin
        simp:=(n mod i <>0);
        if simp then i:=i+2;
      end;
      Simple:=simp;
    end;
end;

[Legolas]

Всем спасибо.
А насчет изобретения велосипеда, то просто я задачи ищу с помощью поисковиков...