Форум «Всё о Паскале» > Простое число

Помощь - Поиск - Пользователи - Календарь

Полная версия: Простое число

Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи

Legolas

23.05.2005 10:15

Всем привет

Вот насчет задачи:

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

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

Код

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. Задачу не сам делал

Всем заранее спасибо.

klem4

23.05.2005 11:44

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

 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;

hiv

23.05.2005 12:45

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

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

23.05.2005 12:54

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

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 , поясни алгоритм

Бродяжник

23.05.2005 13:03

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

if n=2 then Simple:=false

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

volvo

23.05.2005 13:08

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

hiv

23.05.2005 13:22

Цитата(Бродяжник @ 23.05.05 9:03)

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

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

Цитата(klem4)

всегда 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

24.05.2005 5:37

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

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.