Назовем число “зеркально простым”, если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.
Найти количество “зеркально простых” чисел на промежутке от [latex]a[/latex] до [latex]b.[/latex]
Входные данные
Два числа [latex]a[/latex] и [latex]b[/latex] [latex]( 1\le a, b \le 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 43 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) { int a, b; int number1, number2; int counter = 0; Scanner sc = new Scanner(System.in); a = sc.nextInt(); b = sc.nextInt(); if (a > b) { a += b; b = a - b; a -= b; } if (a == 1) counter--; for (int i = a; i <= b; i++) { number1 = i; boolean f1 = true; boolean f2 = true; for (int j = 2; j*j <= number1; j++) { f1 = ((number1%j)!=0); if (!f1) break; } 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)!=0); if (!f2) break; } if (f2) counter++; } } System.out.format("%d", counter); } } |