Особое число
Число 1997 имеет особые свойства. Будучи простым, оно при разделении его цифр на две любые части также дает простые числа (199 и 7, 19 и 97, 1 и 997). Найти другие подобные числа в диапазоне от 1000 до 2000.
l Идея : Поскольку проверка на то, является ли число простым, производится в нескольких случаях, то ее необходимо оформить в виде функции. Сущность алгоритма состоит в последовательной проверке всех значений от 1000 до 2000 на предмет соблюдения указанного свойства (полный перебор). Разделить число на две части можно, используя частное и остаток от его деления на степени 10, то есть 10,100,1000.
l Фактыl :
1. Алгоритм проверки - является ли число простым, приведен в тестовых вопросах предыдущего параграфа. Число a простое, если оно не делится ни на одно из чисел в диапазоне от 2 до a-1 . Это свойство всеобщности проверяется циклом с break.
for (i=2; i<a; i++) if (a%i==0) break;
if (a==i)... // выход по a==i без break - не было ни одного деления
2. . Этот фрагмент оформляется в виде функции, возвращающей логическое значение 0 /1.
int PR(int a)
{ int i;
for (i=2; i<a; i++) if (a%i==0) break;
if (a==i) return 1; else return 0;
}
3. Усовершенствование : завершить функцию с результатом 0 можно сразу же по обнаружении факта деления нацело. Кроме того, функция не проверяет значение 1, которое также является простым числом.
int PR(int a)
{ int i;
if (a==1) return 1;
for (i=2; i<a; i++) if (a%i==0) return 0;
return 1;
}
4. Сам процесс поиска состоит в полном переборе значений в заданном диапазоне.
void main()
{
for (int n=1000; n< 2000; n++)
{ ... Удовлетворяет ли n - условиям
if (удовлетворяет ) cout << n << endl;
}
}
5. Разделить число n на две части и проверить, являются ли они простыми, можно, используя частное и остаток от его деления на степень 10, например
int v=100;
n / v - число без двух младших цифр
n % v - число из двух младших цифр
6. Получить подряд степени числа 10 можно следующим циклом :
for (int v=10; v<n; v*=10) { ...n/v...n%v...}
7. Проверить, являются ли простыми все части, на которые делится число n, можно с помощью цикла проверки свойства ВСЕОБЩНОСТИ
for (int v=10; v<=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v>n) ... // Не было выхода по break (свойство : число простое )
8. Оператор continue досрочно завершает шаг цикла и переходит к следующему, его можно использовать, если в результате проверки оказывается, что число n не удовлетворяет одному из условий. Тогда последовательность конструкций if ( условие не соблюдается ) continue; позволяет организовать " сито" проверок
{
if (!PR(n)) continue; // пропустить - число не простое
for (int v=10; v<=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v<=n) continue; // пропустить - был выход по break
cout << n << endl; // прошли сквозь сито - найдено число
}
Практически программа уже написана, остается составить ее из частей.
