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


Особое число


Число 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 можно следующим циклом :




Начало  Назад  Вперед