Algoholic.in.ua

Решения > "Зеркально простые" числа

"Зеркально простые" числа С++

Категория: Решения | Добавлено: 2015-09-04 | Просмотров: 896

Назовем число "зеркально простым", если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.


Найти количество "зеркально простых" чисел на промежутке от a до b.


Входные данные.


Два числа a и b (1 ≤ a,b ≤ 10000).


Выходные данные.


Вывести количество "зеркально простых" чисел на промежутке от a до b включительно.


Идея решения:


  1. Отсортируем а и b по возрастанию.
  2. Воспользуемся решетом Эратосфена для нахождения всех простых чисел на отрезке.
  3. Если число простое, находим зеркальное ему число и проверяем его на простоту.
  4. Если данная проверка дала позитивный результат - увеличиваем количество "зеркально простых" на 1.

Решение на C++

          #include <iostream>
          #include <vector>
          using namespace std;
          int main()
          {
              int a,b,am=0;
              cin >> a >> b;
              //1
              if (a > b){am = a; a = b; b = am;}
              am=0;
              vector<bool> prime (b + 1, true);
              prime[0] = prime[1] = false;
              if(a <= 2)am++;
              //2
              for (int i = 3; i <= b; i += 2){
                  if (prime[i]){
                      for (int j = 3; i * j <= b; j += 2)
                          prime[j * i] = false;
                          //3
                      if(i >= a){
                          int aMirror = 0,temp;
                          temp  = i;
                          while(temp > 0){
                              aMirror *= 10;
                              aMirror += (temp % 10);
                              temp /= 10;
                          }
                          int sign = 0;
                          if(aMirror % 2 != 0){
                              for(int k = 3; k * k <= aMirror; k += 2){
                                  if(aMirror % k == 0){sign = 1; break;}
                              }
                          }
                          else sign = 1;
                          //4
                          if(sign == 0) am++;
                      }
                  }
              }
              cout << am << endl;
              return 0;
          }
        

Пример 1:
Входные данные:
10 25
Выходные данные:
3
Пример 2:
Входные данные:
1 10000
Выходные данные:
260


Источник условия:
http://www.e-olymp.com/ru/problems/22


Яндекс.Метрика
Украина онлайн