Назовем число «зеркально простым», если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.
Найти количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex].
Входные данные
Два числа [latex]a[/latex] и [latex]b[/latex] ( [latex]1[/latex][latex]\le[/latex] [latex]a[/latex], [latex]b[/latex] [latex]\le[/latex] [latex]10000[/latex]).
Выходные данные
Вывести количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.
Задача взята с сайта e-olymp.
Тесты
| Границы промежутка | Количество «зеркально простых» чисел |
| 1 10 | 4 |
| 100 200 | 12 |
| 1008 1230 | 19 |
| 3340 3950 | 31 |
| 9900 10000 | 4 |
Алгоритм
Перед нами была поставлена задача реализовать поиск всех «зеркально простых» чисел на заданном промежутке. Проверив в правильном ли порядке введены границы промежутка, организуем последовательный анализ для каждого числа из промежутка в теле главного цикла :
- Инициализируем две логические переменные, значение которых отвечает за прохождение теста на простоту самим числом и «зеркальным» соответственно.
- Методом последовательного перебора делителей определяем является ли данное число простым. Если данное утверждение истинно, переходим к последующим пунктам. В противном случае переходим на новый виток главного цикла.
- Выполняем последовательную сборку числа, записанного в обратном порядке.
- Проводим аналогичную проверку на простоту для «зеркального» числа.
- При условии, что это число также является простым, инкрементируем счетчик.
Достигнув верхней границы промежутка, выводим количество «зеркально простых» чисел.
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> using namespace std; int main() { int a, b; int number1, number2;// переменные для хранения текущего числа из промежутка и "зеркального" соответственно int counter = 0;// счетчик количества "зеркально простых" чисел cin >> a >> b; if(a > b){ a += b; b = a - b; a -= b; }// меняем местами границы промежутка, если они введены в неправильном порядке if (a == 1) counter--;// декрементируем счетчик, если в промежуток попадает число 1, которое не является простым for (int i = a; i <= b; i++){ number1 = i; bool f1 = true;// флаг выполнения условия для number1 bool f2 = true;// флаг выполнения условия для number2 for (int j = 2; j*j <= number1; j++){ f1 = number1%j; if (!f1) break; }// проверяем является ли number1 простым if (f1){ number2 = 0; while (number1 > 0){ number2 = number2*10 + number1%10; number1 /= 10; }// собираем число "зеркальное" текущему for (int j = 2; j*j <= number2; j++){ f2 = number2%j; if (!f2) break; }// проверяем является ли number2 простым if (f2) counter++;// инкрементируем счетчик } } cout << counter; return 0; } |