Колганов Роман Антольевич Поромов Сергей Сергеевич - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Колганов Роман Антольевич Поромов Сергей Сергеевич - страница №1/1

Колганов Роман Антольевич

Поромов Сергей Сергеевич

Ульянцев Владимир Игоревич

Царев Федор Николаевич

ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ИНФОРМАТИКЕ И ПРОГРАММИРОВАНИЮ

Этой статьей мы продолжаем цикл публикаций олимпиадных задач для школьников по информатике и программированию с разборами. Решение таких задач и изучение разборов поможет Вам лучше подготовиться к олимпиадам по информатике.

В этой статье рассматривается задача «Обобщенные числа-близнецы», которая предлагалась в четвертой Интернет-олимпиаде сезона 2009-2010 (олимпиада состоялась 31 октября 2009 года). Интернет-олимпиады по информатике проводятся Санкт-Петербургским государственным университетом информационных технологий, механики и оптики в двух номинациях – базовой и усложненной. Базовая номинация рассчитана на начинающих участников олимпиад, поэтому в ней предлагаются более простые задачи, а в усложненной номинации предлагаются задачи уровня городских и всероссийских командных олимпиад по программированию. Сайт этих олимпиад находится по адресу http://neerc.ifmo.ru/school/io/.

Условие задачи


В теории чисел простыми числами-близнецами называют пару таких простых чисел (p, q), что qp = 2. Например, пары (3, 5) и (11, 13) являются парами простых чисел-близнецов. Назовем обобщенными числами-близнецами пару простых чисел (p, q), где qp = k, k – некоторое натуральное число. Например, для k = 4 пара (3, 7) является парой обобщенных чисел-близнецов.

Существует предположение, что пар простых чисел-близнецов бесконечно много, однако это не доказано. Безусловно, выяснить по заданному k, сколько пар обобщенных близнецов содержит множество всех натуральных чисел, не менее сложная задача, чем аналогичная о «обычных» близнецах.

Ваша же задача несколько проще – выяснить по заданному k, сколько пар обобщенных близнецов содержит множество натуральных чисел от 1 до n.

Формат входного файла

Во первой строке входного файла через пробел заданы два натуральных числа n и k (1 ≤ n, k ≤ 104).

Формат выходного файла

В выходной файл выведите число пар простых чисел (p, q), таких, что 1  p < q  n и qp = k.

Примеры входных и выходных данных

twins.in


twins.out

17 2

3

10000 1

1

20 7

0

Разбор задачи


Для начала, заметим, что всего возможных пар натуральных чисел, не превышающих n и различающихся на k ровно nk. Так как ограничения на n и k сравнительно невилики, то решение будет основано на переборе и проверке всех ткаих пар. Напомним, что число m является простым, если оно делится нацело только на себя и на 1.

Легко заметить, что если число m не является простым (такие числа называются составными), то оно делится на некоторое k, большее 1, но меньшее, либо равное квадратному корню из m. Потому, для проверки числа на простоту достаточно написать следующую функцию (листинг 1).



Листинг 1. Функция проверки числа на простоту (язык программирования Pascal)
function isPrime(m : integer) : boolean;

var

i : integer;



begin

i := 2;


while (i * i <= m) do begin

if (m mod i = 0) then begin

isPrime := false;



exit;

end;

end;

isPrime := true;



end;

Эта функция работает за . Поэтому, если с ее использованием проверить на простоту все nk пар чисел-кандидатов, то суммарное время работы будет . Такое решение укладывается в заданные ограничения по времени.

Основной код программы будет выглядеть следующим образом (листинг 2).



Листинг 2. Основной код программы (язык программирования Pascal)
read(n, k);

ans := 0;



for i := 2 to n - k do begin

if (isPrime(i)) and (isPrime(i + k)) then begin

ans := ans + 1;



end;

end;

writeln(ans);

В заключение отметим, что, используя решето Эратосфена [1] для проверки чисел на простоту, время работы алгоритма можно улучшить до O(n log log n). Детальная разработка и реализация этого подхода остается читателю в качестве упражнения.


Источники

1. Статья «Решето Эратосфена» в Википедии. http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0


Информация об авторах:

Колганов Роман Александрович – студент третьего курса кафедры «Компьютерные технологии» СПбГУ ИТМО, член жюри Интернет-олимпиад по информатике базового уровня, преподователь спецкурса «Олимпиадное программирование» гимназии №261 Санкт-Петербурга

Поромов Сергей Сергеевич – студент четвертого курса кафедры «Компьютерные технологии» СПбГУ ИТМО, финалист чемпионата мира по программированию среди студентов 2010 года, член жюри Интернет-олимпиад по информатике базового уровня.

Ульянцев Владимир Игоревич – студент четвертого курса кафедры «Компьютерные технологии» СПбГУ ИТМО, член жюри Интернет-олимпиад по информатике базового уровня.



Царев Федор Николаевич – аспирант кафедры «Компьютерные технологии» СПбГУ ИТМО, чемпион мира по программированию среди студентов 2008 года, член жюри Интернет-олимпиад по информатике базового уровня.