Информатика и технология программирования

       

Особое число


Число 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&#60a; 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&#60a; 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&#60a; i++) if (a%i==0) return 0;
return 1;
}

4. Сам процесс поиска состоит в полном переборе значений в заданном диапазоне.


void main()
{
for (int n=1000; n&#60 2000; n++)
{ ... Удовлетворяет ли n - условиям
if (удовлетворяет ) cout &#60&#60 n &#60&#60 endl;
}
}

5. Разделить число n на две части и проверить, являются ли они простыми, можно, используя частное и остаток от его деления на степень 10, например


int v=100;
n / v - число без двух младших цифр
n % v - число из двух младших цифр

6. Получить подряд степени числа 10 можно следующим циклом :



for (int v=10; v&#60n; v*=10) { ...n/v...n%v...}

7. Проверить, являются ли простыми все части, на которые делится число n, можно с помощью цикла проверки свойства ВСЕОБЩНОСТИ

for (int v=10; v&#60=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v&#62n) ... // Не было выхода по break (свойство : число простое )







8. Оператор
continue досрочно завершает шаг цикла и переходит к следующему, его можно использовать, если в результате проверки оказывается, что число n не удовлетворяет одному из условий. Тогда последовательность конструкций if ( условие не соблюдается ) continue; позволяет организовать " сито" проверок

{
if (!PR(n)) continue; // пропустить - число не простое

for (int v=10; v&#60=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v&#60=n) continue; // пропустить - был выход по break

cout &#60&#60 n &#60&#60 endl; // прошли сквозь сито - найдено число

}

Практически программа уже написана, остается составить ее из частей.




Содержание раздела