Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.08.2019, 23:52   #1
Stalin2019
Пользователь
 
Регистрация: 08.08.2019
Сообщений: 20
По умолчанию [Pascal] Простое

Решить нужно на языке Pascal.
Задача такая:
По данному простому числу найти следующее за ним простое.
Мои мысли по задаче:
пусть мы вводим какое-то m простое

По теореме Чебышева между m и 2m обязательно найдется простое число, если m>=2 . Обнулим k:=0 { Будет отвечать за число делителей числа}

поэтому можно начать перебор for i:= (m+1) to 2*m do

для каждого из i можно начать перебор

for j:=1 to 2*m do

if i mod j=0 then

k:=k+1;

Воот и делать проверку до тех пор пока k<>2

Как только k=2 сразу напечатать i, при котором это произошло
Алгоритм в непричесанном виде

я пробовал все это реализовать, что-то не вышло
Stalin2019 вне форума Ответить с цитированием
Старый 09.08.2019, 00:58   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

перебор с проверкой на простоту у Вас неправильно написан
возьмите код отсюда - https://www.programmersforum.ru/show...58&postcount=4
Serge_Bliznykov вне форума Ответить с цитированием
Старый 09.08.2019, 01:46   #3
Stalin2019
Пользователь
 
Регистрация: 08.08.2019
Сообщений: 20
По умолчанию Простота

Сейчас написал, прога определяет простоту, но мне нужно находить простое из промежутка:
Код:
program prostoe;
uses crt;
var
   n,i,k:integer;
begin
write('Введите число:');
readln(n);
k:=0;
for i:=1 to n do
if n mod i=0 then k:=k+1;
if k=1 then
begin
writeln('Число не является ни простым, ни составным');
halt;
end;
if (k=2) then writeln('Данное число простое')
else writeln('Данное число составное, число делителей равно: ',k);
end.
______________________
Форматируйте код и используйте тег [CODE] (кнопка [CODE] в форме сообщения) при вставке кода на форум. Подробнее в FAQ

Последний раз редактировалось Вадим Мошев; 09.08.2019 в 08:39.
Stalin2019 вне форума Ответить с цитированием
Старый 09.08.2019, 10:21   #4
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Твой фрагмент определения простоты надо сделать в виде функции, которая возвращает логическое значение, например True - если число простое.
Далее организуете цикл от вашего заданного простого m до 2 * m.
В цикле каждое следующее число передаётся в функцию. Если функция вернула True, то печатаешь число и выходишь из цикла по Break.
1. При написании функции нужно вместо вывода сообщений вставить оператор return, предварительно присвоив функции логическое значение.
Код:
function Prostoe(a: integer): boolean;
var i, k: integer;
begin
...
   if k = 2 then begin
      Prostoe := True;
      Break;
   end;
...
end ;
2. Нет смысла проверять делимость от 1 до n. Достаточно до int(sqrt(n)).
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 09.08.2019, 11:10   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Stalin2019 Посмотреть сообщение
Сейчас написал
т.е. по моей ссылке Вы не ходили.
ну, дело ваше.


Цитата:
Сообщение от Stalin2019 Посмотреть сообщение
но мне нужно находить простое из промежутка:
ну так очевидно же:

https://ideone.com/hUCbBZ

Код:
function isPrime(X: LongInt): boolean; {проверка числа на простоту}
var i, mborder: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     mborder := trunc(sqrt(x));
     while i <= mborder  do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;


var m : longint;
  flag:boolean;
begin
   repeat
      WriteLn('Введите простое число m:');
      ReadLn(m);
      flag := isPrime(m);
      if Not flag then WriteLn('Неверно. Число ',m,' составное!');
   until flag;
   repeat
     inc(m);
   until isPrime(m);
   WriteLn('следующее простое число: ',m);
   readln;
end.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 09.08.2019, 12:08   #6
Stalin2019
Пользователь
 
Регистрация: 08.08.2019
Сообщений: 20
По умолчанию

А как сделать без введения функции, я еще не изучал их?В моем расположении максимум: все виды циклов.
Stalin2019 вне форума Ответить с цитированием
Старый 09.08.2019, 12:16   #7
Stalin2019
Пользователь
 
Регистрация: 08.08.2019
Сообщений: 20
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Твой фрагмент определения простоты надо сделать в виде функции, которая возвращает логическое значение, например True - если число простое.
Далее организуете цикл от вашего заданного простого m до 2 * m.
В цикле каждое следующее число передаётся в функцию. Если функция вернула True, то печатаешь число и выходишь из цикла по Break.
1. При написании функции нужно вместо вывода сообщений вставить оператор return, предварительно присвоив функции логическое значение.
Код:
function Prostoe(a: integer): boolean;
var i, k: integer;
begin
...
   if k = 2 then begin
      Prostoe := True;
      Break;
   end;
...
end ;
2. Нет смысла проверять делимость от 1 до n. Достаточно до int(sqrt(n)).
Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
т.е. по моей ссылке Вы не ходили.
ну, дело ваше.



ну так очевидно же:

https://ideone.com/hUCbBZ

Код:
function isPrime(X: LongInt): boolean; {проверка числа на простоту}
var i, mborder: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     mborder := trunc(sqrt(x));
     while i <= mborder  do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;


var m : longint;
  flag:boolean;
begin
   repeat
      WriteLn('Введите простое число m:');
      ReadLn(m);
      flag := isPrime(m);
      if Not flag then WriteLn('Неверно. Число ',m,' составное!');
   until flag;
   repeat
     inc(m);
   until isPrime(m);
   WriteLn('следующее простое число: ',m);
   readln;
end.
Мне нельзя еще функции вводить, надо как-то с циклами решать
Stalin2019 вне форума Ответить с цитированием
Старый 09.08.2019, 12:35   #8
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Ну так и организуй цикл в цикле.
Внешний цикл - перебираем тестируемые значения от m до 2 * m
Внутренний цикл - проверяем на простоту.
При проверке на простоту при обнаружении делимости сразу завершаем проверку (не подсчитываем делители: k > 0) и переходим к следующему тестируемому числу.
Если вышли из цикла, в котором тестируем на простоту и k = 0, то тестировалось простое число.
Код:
m := <нач. значение>
fin := 2*m;
while m <= fin do begin  {перебор тестируемых значений}
   k := 0;
   for i := 2 to int(sqrt(m)) do begin  {проверка делимости}
      if <условие делимости> then {делится}
         k := 1;
         Break;
   end;
   if k = 0 then begin  {успешная проверка на делимость}
      <вывод числа>
      Break;
   end;
   m := m + 1;   {продолжаем тестировать}
end;
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 09.08.2019, 12:50   #9
Stalin2019
Пользователь
 
Регистрация: 08.08.2019
Сообщений: 20
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Ну так и организуй цикл в цикле.
Внешний цикл - перебираем тестируемые значения от m до 2 * m
Внутренний цикл - проверяем на простоту.
При проверке на простоту при обнаружении делимости сразу завершаем проверку (не подсчитываем делители: k > 0) и переходим к следующему тестируемому числу.
Если вышли из цикла, в котором тестируем на простоту и k = 0, то тестировалось простое число.
Код:
m := <нач. значение>
fin := 2*m;
while m <= fin do begin  {перебор тестируемых значений}
   k := 0;
   for i := 2 to int(sqrt(m)) do begin  {проверка делимости}
      if <условие делимости> then {делится}
         k := 1;
         Break;
   end;
   if k = 0 then begin  {успешная проверка на делимость}
      <вывод числа>
      Break;
   end;
   m := m + 1;   {продолжаем тестировать}
end;
Работает, только нужно начинать с (m+1)
Stalin2019 вне форума Ответить с цитированием
Старый 09.08.2019, 14:15   #10
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Ну да.
Но проанализируй пост #5 Serge_Bliznykov
В предложенной там версии время перебора сокращается за счёт того, что после проверки на чётность проверяются только нечётные делители.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
вводится число и программа должна сказать ПРОСТОЕ оно или нет (Pascal) diana1995 Помощь студентам 8 13.05.2013 10:45
Простое шифрование alex.snap Помощь студентам 17 02.11.2012 06:19
k-е простое daniil123 Паскаль, Turbo Pascal, PascalABC.NET 0 14.12.2011 23:52
Простое или нет Superlotles Общие вопросы C/C++ 7 13.03.2010 20:30