обо мне
простые числа
it и около it
шавермы
|
Раздел в разработке и наполнении
Пример самой простой программы проверки числа на простоту, которая, само собой, является совсем не оптимальной, но, тем не менее, работает.
pascal
program prime;
var
i, number:integer;
isPrime:boolean;
begin
readln(number); {получить число для проверки}
isPrime:=true;
for i:=2 to number-1 do
if (number mod i=0) then {если остаток от деления равен 0, значит найден делитель}
begin
isPrime:=false; {записать, что число не простое}
break; {прервать цикл, т.к. больше не надо}
end;
writeln(isPrime);
end.
С этой программой многое плохо. Первое: совсем не нужно делить на все числа менее проверяемого, достаточно дойти до квадратного корня. Второе, делить на все числа, включая четные, достаточно делить на простые.
Соответственно, должна получиться программа, которая будет выполнять две задачи:
- найти простые числа, менее квадратного корня проверяемого;
- осуществить, собственно, проверку на простоту.
Программка получше первой
pascal
program prime;
var
number:longint;{число, которое будем проверять на простоту}
primesCount:integer;{количество найденных простых}
primes:array [1..5000] of integer;{массив простых}
isPrime:boolean;{флаг того, является ли число простым}
i,y,stop:integer;{служебные переменные}
begin
{инициализируем массив с простыми}
primes[1]:=2;
primesCount:=1;
{прочитаем номер для проверки}
readln(number);
{начнем искать простые до квадратного корня проверяемого}
stop:=trunc(sqrt(number));
i:=3;
while (i<=stop) do
begin
isPrime:=true;
for y:=1 to primesCount do
begin
isPrime:=((i mod primes[y])<>0);
if (not(isPrime)) then break;
end;
if (isPrime) then
begin
primesCount:=primesCount+1;
primes[primesCount]:=i;
end;
i:=i+2;
end;
{и, наконец, проверим собственно наше число}
isPrime:=true;
for i:=1 to primesCount do
begin
isPrime:=((number mod primes[i])<>0);
if (not(isPrime)) then break;
end;
writeln(isPrime);
end.
Что в этой программе можно поправить? Например, проверить число на четность сразу после чтения и убрать из массива простых двойку, всё равно проверяются только нечетные.
Теперь приступим к проверки на простоту числа произвольной длины (ну не совсем произвольной, а выходящего за размерность стандартных типов).
Алгоритм работы будет абсолютно таким же, как и во втором примере. Проблемы, которые возникают у новичков с этой задачей, собственно, с простыми числами не связаны.
Разобъем её на подзадачи:
- Запись в память чисел больших (выходящих за пределы стандартных типов) размеров;
- Cравнение больших чисел;
- Деление по модулю больших чисел;
- Поиск квадратного корня большого числа.
продолжение следует... автор устал...
|