Задача Kingdoms2020. Автори казок знають, що є ще царства окрім Тридев'ятого, і вони характеризуються як (N,K) - Царства. Але існувати (N,K) - Царство може лише тоді, коли K може бути представлено у вигляді суми не більше ніж N простих чисел.
Наприклад, (3,9) - (Тридев’яте) Царство існує, тому що 9 = 2 + 7 (ще варіанти: 9 = 3 + 3 + 3 і 9 = 2 + 2 + 5). Також має право на існування і (2,10)- (Двадесяте) Царство, так як 10 = 5 + 5. У той же час (2,27)-е (Двадвадцатьсьоме) Царство існувати не може, оскільки 27 неможливо представити у вигляді суми не більше чим двох простих чисел.
Знайдіть кількість існуючих (N, K)-царств за умови, що числа N і K можуть змінюватися в деякому діапазоні: a ≤ N ≤ b, c ≤ K ≤ d.
Технічні умови. Програма Kingdoms2020 читає з пристрою стандартного введення чотири цілі числа в одному рядку через пропуски: a і b - нижнє і верхнє обмеження на N. Та цілі числа c і d - нижнє і верхнє обмеження на K. Програма виводить на пристрій стандартного виведення єдине число, рівне кількості існуючих (N, K)-царств, для яких a ≤ N ≤ b і c ≤ K ≤ d. Розмір тексту розв’язку не повинен бути більшим 16 Кб.
Обмеження:
1. Число a від 1 до 1000000 включно.
2. Число b від a до a + 1000 включно.
3. Число c від 1 до 1000000 включно.
4. Число d від c до c + 1 000 включно.
Приклади
|
Введення |
Виведення |
Коментарі |
|
1 1 2 10 |
4 |
У цьому прикладі нам необхідно знайти числа K, які представляються у вигляді суми не більше 1-го простого числа, тобто є простими. На відрізку від 2 до 10 включно є 4 простих числа - 2, 3, 5 і 7. |
|
1 2 20 30 |
12 |
(N, K)-царства існують:
Всього маємо 2 + 10 = 12 царств. |
|
2 4 45 64 |
58 |
|
|
1 20 469588 470425 |
15701 |
|
Додаткова інформація
Цитата з однієї, дуже відомої, «казки»: «Натуральне число X, більше одиниці, називається простим, якщо воно не ділиться без остачі ні на які числа, окрім 1 і X.»