Задачи с простыми числами.
Представлен ряд задач, связанных с простыми числами - натуральными (целыми положительными) числами, большими 1, не имеющими других делителей, кроме самих себя и единицы.
Рассмотрим сначала такую задачу:
Задача 1. <Дано натуральное число n. Проверить, является ли оно простым>.
Метод решения этой задачи очевиден. Если n - четное, то оно не простое (составное), иначе следует проверить, являются ли делителем n числа 3, 5, 7,...,n/3 (проверять до n-1 и даже до n/2 нет необходимости), и если хотя бы для одного числа ответ будет положительным, то число n - составное. Заметим при этом, что число 2 - простое.
Программа на школьном алгоритмическом языке имеет вид:
алг Проверка нач цел n,i, лог simp | вывод нс, "n=" | ввод n | если n=2 | |то вывод нс, "Это число простое" | |иначе | | если mod(n,2) = 0 |n - четное число | | |то вывод нс, "Это число составное" | | |иначе | | | simp:=да | | | нц для i от 3 до div(n,3) шаг 2 | | | | если mod(n,i)=0 |встретился делитель числа n | | | | |то simp:=нет | | | | все | | | кц | | | если simp | | | |то вывод нс, "Это число простое" | | | |иначе вывод нс, "Это число составное" | | | все | | все | все кон
Можно ускорить вычисления и проверять делимость n на еще меньшее количество чисел - до квадратного корня из n. Если среди проверенных чисел нет делителей числа n, то их нет и среди остальных нечетных чисел. Можно также прекратить вычисления после того, как только встре-тился делитель числа n. С учетом этого приведенная выше программа мо-жет быть модифицирована путем замены имеющегося в ней цикла на следую-щий:
... simp:=да i:=3 нц пока i<=int(sqrt(n)) и simp | если mod(n,i)=0 |встретился делитель числа n | |то simp:=нет | |иначе i:=i+2 | все кц ...
а функция, проверяющая, является ли число n простым, и возвращаю-щая результат логического типа, имеет вид:
алг лог Simple(арг цел n) нач цел i, лог simp |simp=нет, если встретится делитель числа n | если n=2 | |то знач:=да |значение функции | |иначе | | если mod(n,2) = 0 | | |то знач:=нет | | |иначе | | | simp:=да | | | i:=3 | | | нц пока i<=int(sqrt(n)) и simp | | | | если mod(n,i)=0 | | | | |то simp:=нет | | | | |иначе i:=i+2 | | | | все | | | кц | | | если simp | | | |то знач:=да | | | |иначе знач:=нет | | | все | | все | все кон
Язык Паскаль:
Uses CRT;
Var n: longint;
Function Simple(n:longint):boolean;
Var i:longint;simp : boolean { simp=false, если встретился делитель числа n} ;
begin
if n=2 then Simple:=true
else if n mod 2 = 0 then Simple:=false
else begin
simp:=true;
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
end;
Основная часть программы:
BEGIN
clrscr;
readln(n);
if Simple(n) then writeln('Yes') else writeln('No')
END.
Задача 2. Даны натуральные числа a,b (a<=b). Получить все простые числа p, удовлетворяющие неравенствам a<=p<=b.
Сделаем несколько предварительных замечаний.
Очевидно, что при решении задачи в качестве возможных "кандида-тов" в простые числа можно рассматривать только нечетные числа из ин-тервала a<=n<=b, а также число 2, если оно входит в этот интервал. За-метим также, что возможен случай a=1 и что число 1 простым не счита-ется (по определению).
Основные величины, используемые в программах (кроме величин a и b):
- n - число, проверяемое на "простоту";
- first - начальное значение этого числа;
- simp - величина логического типа, в зависимости от которой дается ответ на вопрос, явля-ется ли число n простым.
- k - количество найденных простых чисел в исследуемом интервале.
Основные этапы решения задачи:
- Ввод значений a и b.
- Проверка принадлежности числа 2 интервалу a<=2<=b (что возмож-но при a=1 или a=2).
- Определение значения first. Если a - четное число, то first=a+1, если нечетное - то first=3, если a=1 и first=a, если a>=3.
- Проверка всех нечетных чисел n от first до b и вывод на экран простых из них (с подсчетом значения k).
Если величина k=0, то это значит, что в указанном интервале простых чисел нет.
Приведем сначала программу с вложенными циклами.
Var a, b, n, first, k, i: integer; simp:boolean;
BEGIN
a:=2; b:=1; {условно для выполнения цикла}
while a>b do begin
write('a='); readln (a);
write('b='); readln (b);
if a>b then writeln('Число a не должно быть больше числа b!')
end;
if (a=1) or (a=2) then begin
write(2,' ');
k:=1
end;
if a mod 2 =0 then first:=a+1 {поиск начинаем с нечетного числа}
else if a=1 then first:=3
else first:=a;
n:=first;
while n<= b do begin
simp:=True;
i:=3; {первый возможный делитель числа n}
while (i<=trunc(sqrt(n))) and simp do
if n mod i=0 then simp:=False
else i:=i+2;
if simp then begin
write(n,' ');
k:=k+1
end;
n:=n+2 {поиск ведем только среди нечетных чисел}
end;
if k=0 then writeln('В этом диапазоне простых чисел нет')
END.
Читаемость приведенной программы значительно улучшается, если про-верку числа n на "простоту" проводить с помощью функции (процедуры), возвращающей результат логического типа. Эта функция отличается от описанной в Задаче 1, тем, что в ней иссле-дуются только нечетные числа.
Школьный алгоритмический язык:
алг лог Simple(арг цел n) нач цел i, лог simp |simp=нет, если встретится делитель числа n | simp:=да | i:=3 | нц пока i<=int(sqrt(n)) и simp | | если mod(n,i)=0 | | |то simp:=нет | | |иначе i:=i+2 | | все | кц | если simp | |то знач:=да | |иначе знач:=нет | все кон
Язык Паскаль:
Var a,b,n,first,k:integer;
Function Simple(n:integer):boolean;
Var i:integer;
simp:boolean; {simp=False, если встретится делитель числа n }
begin
simp:=True;
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;
BEGIN
a:=2; b:=1;
while a>b do begin
write('a='); readln (a);
write('b='); readln (b);
if a>b then writeln('Число a не должно быть больше числа b!') end;
if (a=1) or (a=2) then begin
write(2,' ');
k:=1
end;
if a mod 2 =0 then first:=a+1
else if a=1 then first:=3
else first:=a;
n:=first;
while n< b do begin
if Simple(n) then begin
write(n,' ');
k:=k+1
end;
n:=n+2
end;
if k=0 then writeln('В этом диапазоне простых чисел нет')
END.
Примечание. Во всех представленных программах случаи a=1,b=1 и a=1,b=2 не рассматривались.
Задача 3. Найти 100 первых простых чисел.
Как и в задаче 2, приведем сначала программы с вложенными циклами. Основные величины, используемые в программах:
- n - число, проверяемое на "простоту";
- simp - величина, назначение которой описано при разборе задачи 2;
- k - количество найденных простых чисел.
Школьный алгоритмический язык:
алг Задача 3 нач цел n,i,k,лог simp | вывод 2 | k:=1 | n:=3 | нц пока k<100 | | simp:=да | | i:=3 | | нц пока i<=int(sqrt(n)) и simp | | | если mod(n,i)=0 | | | |то simp:=нет | | | |иначе i:=i+2 | | | все | | кц | | если simp | | |то вывод n | | | k:=k+1 | | все | | n:=n+2 | кц кон
Язык Паскаль:
Var n,k,i:integer; simp:boolean; BEGIN write(2,' '); k:=1; n:=3; while k<100 do begin simp:=True; 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 begin write(n,' '); k:=k+1 end; n:=n+2 end; END.
Программа, использующая функцию:
Var n,k:integer;
Function Simple(n:integer):boolean;
... см. задачу 2
end;
BEGIN {Основной части программы}
write(2,' '); k:=1;
n:=3;
while k< 100 do begin
if Simple(n) then begin
write(n,' ');
k:=k+1
end;
n:=n+2
end;
END.
Имеется еще один метод решения рассматриваемой задачи. Он заключается в том, что все найденные простые числа хранятся в некотором массиве, а делимость очередного кандидата проверяется только на числа из этого массива. При этом уменьшается количество возможных делителей, что приводит к ускорению работы программы. Причем и эту проверку можно ускорить, если проверять делимость очередного числа n только на те элементы массива, значение которых не больше квадратного корня из n. Данный метод особенно эффективен в тех случаях, когда необходимо найти большое количество простых чисел.
Приведем программы, в которых применяется этот метод.
Назначение величин k, n и simp в программах аналогично описанному выше. Дополнительно используемые величины:
- find - массив найденных простых чисел (из 100 элементов);
- limit - величина, равная квадратному корню из n.
Школьный алгоритмический язык:
алг Задача 3 нач цел n,i,k, цел таб find[1:100], лог simp, цел limit | find[1]:=2; |записываем в массив простых чисел одно известное | вывод 2 | k:=1 |число найденных простых чисел | n:=3; |первый "кандидат" в простые числа | нц пока k<100 | | limit:=int(sqrt(n)) | | simp:=да | | i:=1 | | нц пока i<=k и simp и find[1]<=limit |условие проверки делимости | | | если mod(n,find[i])=0 | | | |то simp:=нет | | | |иначе i:=i+1 | | | все | | кц | | если simp | | |то | | | вывод n |n - простое число | | | k:=k+1; |добавляем найденное n | | | find[k]:=n |в массив простых чисел | | все | | n:=n+2 |следующий кандидат в простые числа | кц кон
Язык Паскаль:
Var n,i,k:integer; find:array[1..100] of integer; simp:boolean; limit:integer;
BEGIN
find[1]:=2; {записываем в массив простых чисел одно известное}
write(2,' ');
k:=1; {число найденных простых чисел}
n:=3; {первый "кандидат" в простые числа}
while k<100 do
begin
limit:=trunc(sqrt(n));
simp:=true;
i:=1;
while (i<=k) and simp=true and (find[i]<=limit)
{условие проверки делимости числа n}
do if n mod find[i]=0 then simp:=false else i:=i+1;
if simp then begin
write(n,' '); {n - простое число}
k:=k+1; {добавляем найденное n}
find[k]:=n {в массив простых чисел}
end;
n:=n+2 {следующий кандидат в простые числа}
end
END.
Задача 4. Дано четное число n>2; проверить для этого числа гипотезу Гольдбаха. Эта гипотеза (по сегодняшний день не опровергнутая и пол-ностью не доказанная) заключается в том, что каждое четное n, большее двух, представляется в виде суммы двух простых чисел. Определить про-цедуру, позволяющую распознавать простые числа).
Для проверки гипотезы следует определить, имеются ли среди пар чисел 2 и n-2, 3 и n-3,..., n-2 и 2 такие, что числа, их составляющие, - простые.
Приведем сначала программу на школьном алгоритмическом языке. Ве-личины, используемые в ней:
- n - число, применительно к которому проверяется гипотеза;
- item1 - первое число в перечисленных парах чисел;
- k - число пар с простыми составляющими (очевидно, что это число может быть больше 1, например, для n=10: 3 и 7, 5 и 5, 7 и 3).
В программе используется функция Simple, "распознающая" простые числа, описанная в Задаче 1.
алг Задача 4 нач цел n,item1, k | n:=1 |условно для выполнения цикла | нц пока mod(n,2)=1 | | вывод нс,"n=" ; ввод n | | если mod(n,2)=1 | | |то | | | вывод нс,"Число n должно быть четным!" | | все | кц | item1:=3; k:=0 | нц для item1 от 2 до n-2 | | если Simple(item1) и Simple(n-item1) | | |то k:=k+1 | | все | кц | если k>0 | |то вывод нс,"Для данного n гипотеза справедлива" | |иначе вывод нс,"Для данного n гипотеза не справедлива" | все кон
Существенного сокращения числа вычислений можно достичь, если учитывать, что:
- для n>4 возможные значения п р о с т ы х составляющих пар - нечетные числа, т.к. единственным простым четным числом является 2;
- можно рассматривать значения item1 только до n/2 (если в этом интервале нет пар чисел с простыми item1 и n-item1, то их нет и среди остальных значений item1).
- можно прекратить вычисления как только будет найдена первая пара простых чисел.
В программах использована величина hypot логического типа, от ко-торой зависит ответ на вопрос о справедливости гипотезы Гольдбаха. В случае положительного ответа на экран выводится также первая найденная пара простых слагаемых item1 и n-item1.
Школьный алгоритмическй язык:
алг лог Simple(арг цел n) нач ... см. выше кон алг Задача 4 нач цел n,item1, лог hypot | n:=1 | нц пока mod(n,2)=1 или n<4 | | вывод нс,"n=" ; ввод n | | если mod(n,2)=1 | | |то | | | вывод нс,"Число n должно быть четным!" | | все | | если n<4 | | |то | | | вывод нс,"Число n должно быть >2!" | | все | кц | hypot:=нет | если n=4 | |то |проверим и число 4 | | item1:=2 | | hypot:=да | |иначе |n>4 | | item1:=3 | | нц пока item1<=div(n,2) и не hypot | | | если Simple(item1) и Simple(n-item1) | | | |то hypot:=да | | | |иначе item1:=item1+2 | | | все | | кц | все | если hypot | |то вывод нс,"Для данного n гипотеза справедлива" | | вывод нс,"Простыми слагаемыми являются числа", item1,"и",n-item1 | |иначе вывод нс,"Для данного n гипотеза несправедлива"" | все кон
Язык Паскаль:
Var n,item1:integer; hypot:boolean;
Function Simple(n:integer):boolean;
Var i:integer;
simp:boolean; {simp=False, если встретится делитель числа n}
begin
if n=2 then Simple:=True
else if n mod 2=0 then Simple:=False
else begin
simp:=True;
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;
end;
BEGIN
n:=1; {условно для выполнения цикла}
while n mod 2 = 1 do
begin
write('n='); readln (n);
if n mod 2 = 1 then writeln('Число n должно быть четным!')
end;
hypot:=False;
if n=4 then begin {проверяем и число 4}
item1:=2;
hypot:=True
end
else begin {n>4}
item1:=3;
while (item1<=n div 2) and not hypot do
if Simple(item1) and Simple(n-item1) then hypot:=True
else item1:=item1+2
end;
if hypot then
begin
writeln('Для данного n гипотеза справедлива');
writeln('Простыми слагаемыми являются числа ',item1,' и ',n-item1) end
else writeln('Для данного n гипотеза не справедлива');
END.
Задача 5. Дано натуральное число n. Выяснить, имеются ли среди n, n+1, ..., 2n близнецы, т.е. простые числа, разность между которыми равна двум. (Определить процедуру, позволяющую распознавать простые числа).
Величины, используемые в программах (кроме величины n): m - число, проверяемое на "простоту";
- first - начальное значение этого числа;
- k - число пар "близнецов", найденных в рассматриваемом интервале.
Основные этапы решения задачи:
- Ввод значения n.
- Определение значения first (см. задачу 1).
- Поиск чисел-близнецов среди нечетных чисел m от first до 2n и вывод их на экран (с подсчетом количества).
Школьный алгоритмический язык:
алг лог Simple(арг цел n) нач ... см. задачу 1 кон алг Задача 5 нач цел n, first, m, k | вывод нс,"n=" ; ввод n | вывод нс, "Числа-близнецы" | если mod(n,2)=0 | |то first:=n+1 |поиск начинаем с нечетного числа | |иначе first:=n | все | k:=0 | нц для m от first до 2*n-2 шаг 2 |и ведем среди таких же чисел | | если Simple(m) и Simple(m+2) | | |то вывод m,"и",m+2 | | | k:=k+1 | | все | кц | если k=0 |например, при n=6 | |то вывод "в рассматриваемом диапазоне отсутствуют" | все кон
Язык Паскаль:
Var n,m,first,k:integer;
Function Simple(n:integer):boolean;
... (см. задачу 2)
end;
BEGIN
write('n='); readln (n);
write('Числа-близнецы ');
if n mod 2 =0 then first:=n+1
else first:=n; {поиск начинаем с нечетного числа}
m:=first;
while m<2*n-2 do
begin
if Simple(m) and Simple(m+2) then
begin
write(m,' и ',m+2,' ');
k:=k+1
end;
m:=m+2 {и ведем среди таких же чисел}
end;
if k=0 {например, при n=6}
then write('в рассматриваемом диапазоне отсутствуют')
END.
Примечание. В условии задачи требовалось только ответить на вопрос, имеются ли близнецы в указанном диапазоне чисел. При необходи-мости строгого соблюдения условий задачи можно не выводить найденные значения близнецов на экран, а выводить только ответ на вопрос в за-висимости от значения k. При этом можно также прекратить поиск после нахождения первой пары чисел-близнецов.
Нетрудно заметить, что в представленных программах значение функции (или величины) Simple для каждого значения m определяется дважды, что нерационально. Этот недостаток можно устранить, если использовать величину was_simple логического, определяющую, являлось ли простым число, пред-шествовавшее расcматриваемому числу m. Естественно, что в этом случае следует проверять значения m до 2n, а не до 2n-2, как это делалось ра-нее.
Школьный алгоритмический язык:
алг лог Simple(арг цел n) нач ... см. выше кон алг Задача 5 нач цел n,first,m,k, лог was_simple | вывод нс,"n=" ; ввод n | вывод нс, "Числа-близнецы" | если mod(n,2)=0 | |то first:=n+1 | |иначе first:=n | все | k:=0 | was_simple:=нет | нц для m от first до 2*n шаг 2 | | если Simple(m) | | |то | | | если was_simple | | | |то | | | | вывод m-2,"и",m | | | | k:=k+1 | | | все | | | was_simple:=да | | |иначе | | | was_simple:=нет | | все | кц | если k=0 | |то вывод "в рассматриваемом диапазоне отсутствуют" | все кон
Язык Паскаль:
Var n,m,first,k:integer; was_simple:boolean;
Function Simple(n:integer):boolean;
... см. выше
end;
BEGIN
write('n='); readln (n);
write('Числа-близнецы ');
if n mod 2 =0 then first:=n+1
else first:=n;
m:=first;
while m<2*n do
begin
if Simple(m) then begin
if was_simple then
begin
write(m-2,' и ',m,' '); k:=k+1
end;
was_simple:=True
end
else was_simple:=False;
m:=m+2
end;
if k=0 then write('в рассматриваемом диапазоне отсутствуют')
end.
mailto:zlato@orc.ru
Оставить комментарий
Комментарии
Попробую восполнить для простых чисел.
Итак имеем по определению: простое число -- целое число большее 1 и которое делится без остатка только на 1 и на себя. Т.е. простые числа: 2, 3, 5, 7 и т.д.
Для оптимизации алгоритмов проверки простых чисел можно использовать несколько соображений (применяются в статье, здесь привожу с доказательством):
1)Простое число -- нечетное число (за исключением числа 2, которое простое).
Доказательство очевидно, поскольку все четные кратны двум, а значит уже делимы
без остатка хотя бы на двушку.
2)Если число составное, то его можно представить в виде произведения целых a=m*M;
значит корень(a)=корень(m*M), т.е. сред. геометрическому; значит корень(а) лежит
между m и M. Поэтому, "забраковать" число как не простое можно выполнив проверки
лишь для чисел <= корня от него.
3)Нечетное число делится на четное с остатком. Действительно, предположим,
что верно обратное, тогда нечетное (2m+1) при делении на четное (2n) должно
дать целое (k), т.е. (2m+1)/(2n) = k. Это равносильно тому, что (2m+1)=2nk.
Но 2nk четное. Получили противоречие: нечетное равно четному.
Ну и пример от себя на C++ в обобщение сказанного:
Функция проверки простых чисел.
[code/]
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//цикл по нечетным от 3 до i=корень(с);
//c=3, 5 и 7 этот цикл пропустят, но им
//можно - они простые :)
for (int i = 3; i*i <= c; i+=2)
if (!(c % i))
return false;
return true;
}
[/code]
Здесь сравнение с корнем заменено на более быструю эквивалентную конструкцию
i*i <= c (равносильно i<=корень(с))
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
//один раз корень посчитать быстрее, чем i*i сравнивать с c в цикле
int im = (int)sqrt(c) + 1; //+1 чтобы не писать <= im
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
bool prime(int c) {
if (c < 2) return false;
if (c == 2) return true;
if (!(c % 2)) return false;
int im = (int)ceil(sqrt(c)) + 1; //+1 чтобы не писать <= im;
//c=3 этот цикл пропустит, но ей можно (3-простое)
for (int i = 3; i < im; i+=2)
if (!(c % i)) return false;
return true;
}
