Задача 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)-царства існують:

  • при N = 1 - для K = 23, 29

  • при N = 2 - для K = 20, 21, 22, 23, 24, 25, 26, 28, 29, 30

Всього маємо 2 + 10 = 12 царств.

2 4 45 64

58

 

1 20 469588 470425

15701

 

Додаткова інформація

Цитата з однієї, дуже відомої, «казки»:  «Натуральне число X, більше одиниці, називається простим, якщо воно не ділиться без остачі ні на які числа, окрім 1 і X

© LIKT 1998-2018