Тема. Программирование на 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, всегда имеет два делителя (единицу и само это число). Поэтому простым будет такое натуральное число, которое не будет иметь других делителей.
- Среди натуральных чисел только одно четное число является простым (2), все остальные простые числа - нечетные.
- Если не учитывать само число, то у натурального числа нет делителей, которые превышают арифметический квадратный корень из этого числа.
Если использовать указанные свойства, то соответствующий алгоритм может быть таким:
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.
