Четверг, 14.11.2024, 23:25
Главная | Регистрация | Вход Приветствую Вас Гость | RSS


Меню сайта


Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Тестування онлайн
тестування онлайн 


Социальные закладк

Тема. Программирование на  PascalABC.NET 

Задача 1. Нахождение простых чисел.

Составить  алгоритм (затем программу), который будет проверять, является ли введенное число простым.

Напомним,  что  простым  называется  натуральное  число,  которое  имеет ровно два делителя. 

  • Поэтому можно перебрать все натуральные числа от 1  до  данного  числа  и  подсчитать  количество  делителей  данного  числа. 
  • Если это  количество  равно  двум,  то  данное  число  простое,  если  больше  -  не  простое.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители . Если делители есть, число n – составное, если – нет, то – простое.

Вариант 1.

program procti_chicla1;
var k,n,i: Integer;
begin
 k:=0;
 // Количество делителей числа n
 write('введите число ');
 readln(n);
 for i:=1 to n do 
    
       if n mod i = 0 then   
// Проверка, является ли число і делителем числа n
              k:= k+1; //Увеличение на 1 количества делителей числа n, если число і является его делителем
  if k=2  then write(n,'- простое ') else write(n,'- непростое ');
end. 

 

Вариант 2

program procti_chicla2;
var k,n,i: Integer;
begin
 k:=0;
 write('введите число = ');
 readln(n);
 for i:=1 to n do    
      if n mod i = 0 then 
      begin
      k:= k+1;
      writeln('i= ',i,'     ',n ,' mod ' ,i ,' = ', n mod i ,'    k= ',k)
      end;
   if k=2  then write(n,'- простое ') else write(n,'- непростое ');

end.

 


Вариант 3

Но время выполнения программы для решения этой задачи можно существенно уменьшить, если учесть такие свойства натуральных чисел:

  1.  Любое натуральное число, большее 1, всегда имеет два делителя (единицу  и  само  это  число).  Поэтому  простым  будет  такое  натуральное число, которое не будет иметь других делителей.
  2.  Среди натуральных чисел только одно четное число является простым (2), все остальные простые числа - нечетные.
  3.  Если  не  учитывать  само  число,  то  у  натурального  числа  нет  делителей,  которые  превышают  арифметический  квадратный  корень  из  этого числа.

Если использовать указанные свойства, то соответствующий алгоритм  может быть таким:

program procti_chicla3;
var k,n,z: Integer;
f:boolean;

begin
 f:=true; //
Будем пока считать число n простым, ведь делителей у него пока еще не нашлось
 write('введите число  ');
 readln(n);
 if (n mod 2 = 0) and (n<>2)
                     then f:=false 
// Если число n четное и не равно 2, то оно не простое
                     else
                             
begin
                                    k:=3;
//
Если число нечетное, то будем искать его делители, начиная с числа 3

                                   z:=2;//Количество делителей
                                  while (k <= sqrt(n)) and (f= true) do //Искать  делители  числа  будем  среди  чисел,  которые  не  превышают  арифметический  квадратный  корень  из  числа  n,  и  пока такой делитель не нашелся
                                                          begin
                                                                       if n mod k = 0 
// Проверка, является ли число k делителем числа n
                                                                            then 
                                                                             
 begin
                                                                                      f:=false; z:=z+1;
                                                                                      writeln('k= ',k, '   ',n, ' mod ' ,k,' = ',n mod k ,'    f= ' ,f, '  z= ',z);
                                                                             
end
                                                                         else
                                                                           
begin
                                                                                    k:= k+2;
                                                                                    writeln('k= ',k,'     ',n ,' mod ' ,k ,' = ', n mod k ,'  f= ' ,f, '  z= ',z);
                                                                             
end;
                                                          end;
                                          end;
  
 if f=true  then write(n,'- простое ') else write(n,'- непростое ');
end.

Форма входа
Поиск
Календарь
«  Ноябрь 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
252627282930
Архив записей
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Рейтинг@Mail.ru
    Copyright MyCorp © 2024
    Конструктор сайтов - uCoz