Формат входного файла
Файл содержит два натуральных числа A и B(не более 100000)
Формат выходного файла
Файл должен содержать все простые числа большие А и меньшие В разделенные пробелами или переносами строки.
Пример
Input.txt |
Output.txt |
1 3 |
2 |
Если на один тест дается одна секунда, то простой перебор по времени не проходит.
Тогда создадим массив простых чисел меньших 100000 и выбираем из него нужные числа.
program prostie;
const t=9592;
x:array [1..t] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,
.......................................................
99761,99767,99787,99793,99809,99817,99823,99829,99833,99839,99859,99871,99877,99881,99901,
99907,99923,99929,99961,99971,99989,99991);
var a,b,i:longint;
begin
assign(input,'input.txt');
reset(input);
read(a,b);
assign(output,'output.txt');
rewrite(output);
i:=1;
while x[i]<=a do inc(i); ищем индекс первого простого большего a
j:=i;
while (j<t)and(x[j]<b) do пока не вышли за пределы массива и за b
begin
write(x[j],' '); выводим простые числа
inc(j);
end;
close(input);
close(output);
end.
задачи
Задача 12 Сверхпростые числа
Сверхпростым числом называется простое число, сумма цифр которого сама является простым числом. Требуется найти все сверхпростые числа большие А и меньшие В.
Формат входного файла
Файл содержит два натуральных числа A и B(A<=1<=A<=B<=100000).
Формат выходного файла
Файл должен содержать все сверхпростые числа большие А и меньшие В разделенные пробелами или переносами строки.
Пример
-
Input.txt
Output.txt
1 3
2
Добавляем в предыдущее решение функцию находящую сумму цифр числа и функцию, проверяющую число на простоту. Для ускорения работы программы создаем массив простых чисел и бегаем по нему.
program sverxprost;
const t=9592;
x:array [1..t] of longint=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,
199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
……………………………………………………………………………………………………………………………………………………………..
99761,99767,99787,99793,99809,99817,99823,99829,99833,99839,99859,99871,99877,99881,99901,
99907,99923,99929,99961,99971,99989,99991);
function simple(m:longint):boolean; проверка на простоту
var i:longint;
begin
simple:=false;
if m=2 then begin simple:=true; exit end;
if (m=1)or(m mod 2=0) then exit;
i:=3;
while i<=sqrt(m) do
begin
if m mod i=0 then exit
else inc(i,2);
end;
simple:=true;
end;
var i,k,n:longint;
begin
assign(input,'supprime.in');
reset(input);
read(k);
assign(output,'supprime.out');
rewrite(output);
n:=0; счетчик сверхпростых чисел
i:=1;
while n<k do пока не дошли до k-го сверхпростого
if simple(i) проверяем на простоту индекс простого
then
begin inc(n);inc(i);end если индекс простое число, считаем его и
переходим к следующему простому
else inc(i); иначе просто переходим к следующему простому
write(x[i-1]); выводим k-е сверхпростое
close(input);
close(output);
end.
задачи
Задача 13 Разложить данное натуральное число N на простые множители
По основной теореме
арифметики любое натуральное число
можно представить в виде произведения
простых множителей единственным образом.
Порядок множителей значения не имеет.
Представление числа N
в виде: N =
(1),
где a1,
…, ak
– произвольные натуральные числа.
называют каноническим разложением
числа N
на множители.
Возьмем для примера N<=193;
program razlprost;
const p=array[1..44] of integer = простых чисел <=193 всего 44
(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,
61,67,71,73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,179,
181,191,193);
var n,i:integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
for i:=1 to 44 do
while n mod p[i]=0 do
begin
write(p[i],' ');
n:=n div p[i];
end;
end;
end.
Опр. Наибольший общий делитель это наибольшее натуральное число, на которое делятся оба данных числа. Наибольший общий делитель обозначается HОД(а,b).
Опр.
Натуральные числа a
и b
называются взаимно простыми, если НОД(a,
b)=1.
Обозначим через
(N)
количество чисел, взаимно простых с N.
Пусть N
задано в виде (6). Чему равно
(N)?
Оказывается,
(N)
= N(1-
)…(1-
)
.
задачи
Задача 14 Дано натуральное число N (1<=N<=106). Найти последнюю цифру количества всех делителей числа N
Разложим данное натуральное число в произведение простых чисел, используя массив простых чисел из предыдущей задачи. Простых чисел не превышающих 106 всего 78498. Но так как они типа longint, то на Паскале в память массив не помещается. Поэтому с такими ограничениями задачу надо решать на Дельфи.
Если N=p1a1* p2a2*… pnan тогда количество всех делителей числа N равно произведению (1+a1)*(1+a2)*…(1+an)
Показатели степеней простых чисел будем хранить в одномерном массиве. Затем все показатели увеличим на 1. И далее последовательно перемножим элементы массива, беря множители и промежуточный результат по модулю 10, так как нам нужна только последняя цифра..
program poslcifra;
{простых чисел меньше 1000000 всего 78498}
const nmax=100;
p:array[1..78498] of integer=(2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
…………………………………………………………………………………………
999979,999983);
var
s:array[1..nmax]of integer;
t,i,n,res:longint;
function simple(p:longint):boolean;
var i:longint;
begin
simple:=false;
if p=2 then begin simple:=true; exit; end;
if (p=1)or(p mod 2=0) then exit;
i:=3;
while i<=round(sqrt(p)) do
begin
if p mod i=0 then exit
else inc(i,2);
end;
simple:=true;
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
i:=1;t:=1;
while (i<=78498)and(p[i]<=n) do
begin
while n mod p[i]=0 do пока n делится на простое число делим
begin
inc(s[t]); считаем множитель
n:=n div p[i]; уменьшаем n
end;
inc(t); увеличиваем индекс элементов массива
end;
dec(t);
res:=1;
for i:=1 to t do увеличиваем на 1 показатели степеней
inc(s[i]);
for i:=1 to t do находим последнюю цифру
res:=(res*s[i]) mod 10;
close(input);
close(output);
end.
задачи
Задача 15 Количество делителей 2
Пусть x – натуральное число. Назовем число y его делителем, если 1<=y<=x и остаток от деления x на y равен нулю. Дано число x. Найдите количество его делителей, делящихся на каждое из простых чисел, на которые делится x.
Формат входного файла
Первая строка содержит целое число x (1<=x<=1018). Все простые делители числа x не превосходят 1000.
Формат выходного файла
В выходной файл выведите ответ на задачу.
Примеры
Input.txt |
Output.txt |
12 |
2 |
239 |
1 |
Решение на Дельфи
program c;
{$APPTYPE CONSOLE}
Var p:array[1..168] of integer = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277, 281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397, 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997); a:array[1..1000]of longint;
x:int64;
k,i,res:longint;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
read(x);
k:=0;
for i:=1 to 168 do перебираем все возможные простые делители
while x mod p[i]=0 do пока x делится на простое
begin
inc(a[p[i]]); считаем делитель
x:=x div p[i]; делим x на делитель
end;
res:=1;
for i:=1 to 1000 do считаем количество делителей
if a[i]<>0 then res:=res*a[i]; так как каждый делитель может сочетаться с
каждым
write(res);
close(input);
close(output);
end.
задачи
Задача 16 Нахождение наибольшего общего делителя двух натуральных чисел
Аббревиатура НОД расшифровывается как наибольший общий делитель.
Опр. Наибольшим общим делителем данных натуральных чисел- наибольшее натуральное число, на которое делится каждое из этих чисел. Натуральные числа НОД которых равен единице, называются взаимно простыми числами. Рассмотрим алгоритм нахождения наибольшего общего делителя двух чисел.
Определение HОД(а,b) по алгоритму Евклида.
Обозначим d= HОД(а,b).
Пусть a>b. Тогда a=b*q+r отсюда r=a-b*q. Так как a и b делятся на d, то и r делится на d. Тогда
HОД(а,b)= HОД(b,r). Получаем ту же самую задачу, но с меньшими числами, так как b<a и r<b.Этот процесс продолжается до тех пор пока остаток r не обратится в ноль.
Function NOD(a,b:longint):longint; деление с остатком a>=b
Var r:longint;
begin
repeat
r:=a mod b;
a:=b;
b:=r;
until r=0;
NOD := a;
end;
Второй алгоритм
Так как НОД(a,b)= НОД(a mod b,b), если a>=b то функция будет следующая
function NOD(a,b:longint):longint;
begin
while (a<>0)and(b<>0) do
begin
if a > b then a := a mod b
else b := b mod a;
end;
NOD := a+b;
end;
Третий алгоритм нахождения НОД(а,b) рекурсивный.
Function NOD(a , b: longint):longint;
Begin
If (b=0)or(a=0)
then begin NOD:=a+b; exit ;end
else NOD:=NOD(b, a mod b);
end;
Нахождение НОД нескольких чисел.
Var n, i :integer;
…
Read (n); считываем количество чисел
read(a,b); считываем первые два числа
a:=nod(a,b);
For i :=3 to n do
Begin
Read(b); считываем очередное число
a:=NOD(a,b);
End;
Нахождение НОД двух чисел типа extended.
В Паскале тип extended имеет 19-20 значащих цифр, а тип longint только 10. Для нахождения НОД чисел, содержащих от 11 до 20 цифр можно использовать следующую функцию.
var a,b:extended;
function nod(a,b:extended):extended;
begin
while (a>0)and(b>0) do
begin
if a>b
then a:=a-trunc(a/b)*b
else b:=b-trunc(b/a)*a;
end;
nod:=a+b;
end;
begin
a:=15*10e+18; берем для примера два числа a и b.
b:=6*10e+18;
writeln(nod(a,b):0:0); выводим целую часть числа
end.
Используем тот факт, что NOD(a,b)=NOD(a-trunc(a/b)*b), если a>b
и NOD(a,b)=NOD(b-trunc(b/a)*a), если b>a
задачи
Задача 17 Нахождение наименьшего общего кратного натуральных чисел
Опр. Наименьшим общим кратным двух чисел называется наименьшее натуральное число, которое делится на каждое из этих чисел.
Используем формулу: NOK(a,b)=a*b / NOD(a,b);
Function NOK(a, b :longint);
Begin
NOK:=a*b div (NOD(a,b));
End;
найдем НОК более двух чисел, используя функцию NOD(a,b) и тот факт, что
НОД(a,b,c)=НОД(НОД(a,b),c).
Var n, i, um, NOK :integer;
…
Read (n); водим количество чисел
read(a); вводим первые два числа
read(b);
um:=a*b;
a:=nod(a,b); вычисляем НОД двух первых чисел
For i :=3 to n do перебираем остальные числа
Begin
Read(b);um:=um*b;
a:=NOD(a,b);
End;
NOK:=um div a;
задачи
Задача 18 Сложение дробей
Даны натуральные числа a,b,c,d. Найти сумму двух дробей a/b+c/d