Цикл: найти с число с максимальным числом четных делителей - C (СИ)
Формулировка задачи:
Найти натуральное число от 1 до N c максимальным числом четныx делителей.
Решение задачи: «Цикл: найти с число с максимальным числом четных делителей»
textual
Листинг программы
/*
============================================================================
Name : c_struct.c
Author : UranFlex
Version : 0.й alpha
License : Free for all
Copyright : UranFlex 2013
Description : Найти натуральное число от 1 до N c максимальным числом четныx делителей.
* В задаче рассмотрены только положительные четные делители числа, т.е отрицательные не рассматриваются
* C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
// структура для хранения числа и количества его четных положительных делителей
typedef struct {
unsigned value; // число
unsigned countDivisor; // количество четных положительных делителей
} Pair;
// функция возвращает количество положительных четных делителей числа value,
// само value также рассматривается в качестве делителя если value имеет четное значение
// данная функция использует самый простой в реализации алгоритм, но далеко не самый эффективный при выполнении
unsigned CountEvenDivNatNum( const int value );
// функция возвращает структуру, содержащую в своих полях:
// 1) число из диапазона [ 2..value ] c максимальным количеством положительных четныx делителей,
// причем если имеются несколько таких чисел, то берется минимальное из них
// 2) и это максимальное количество четных делителей
// то есть функция будет работать только для натуральных чисел больших 1,
// а для меньших или равных 1 будет возращать структуру, содержащую в своих полях:
// 1) 0
// 2) 0
// так как такие числа не входят в диапазон [ 2..value ]
Pair MaxCountEvenDivNatNum( const int value );
int main( void ) {
// ввод числа
int n;
printf( "Введите целое положительное число большее 1 " );
scanf( "%d", &n );
if ( n < 2 ) { // проверяем чтобы число было не меньше 2
puts( "Ошибка - неверный ввод!" );
return EXIT_FAILURE;
}
// находим искомое число с максимальным числом положительных четных делителей из диапазона [ 2..n ]
// а также само количество этих положительных четных делителей
Pair number = MaxCountEvenDivNatNum( n );
// выводим результаты
printf( "Число из диапазона [ 2..%d ] с максимальным количеством четныx делителей = %u\n", n, number.value );
printf( "Количество его четных положительных делителей = %u\n", number.countDivisor );
return EXIT_SUCCESS;
}
unsigned CountEvenDivNatNum( const int value ) {
int i; // счетчик цикла
// если оно меньше 2, то мы его не рассматриваем
if ( value < 2 || value % 2 ) // или если число нечетное, то оно не имеет четных делителей
return 0; // возвращаем 0
// количество положительных четных делителей числа
unsigned counter = 1; // если число четное, то как минимум есть один положительный четный делитель - оно само
// счетчик цикла увеличиваем на 2 в каждой итерации
for ( i = 2; i <= value / 2; i += 2 ) // так как рассматриваем только положительные четные делители
if ( value % i == 0 ) // если остаток от деления value на 2 равен 0, значит это очередной делитель
++counter; // тогда и увеличиваем количество положительных четных делителей
return counter; // возвращаем количество положительных четных делителей
}
Pair MaxCountEvenDivNatNum( const int value ) {
int i; // счетчик для перебора всех чисел из диапазона [ 2..value ]
Pair sought = { 0, 0 }; // объект для хранения искомого числа и колисества его положительных четных делителей
for ( i = 2; i <= value; ++i ) { // перебираем все числа из диапазона [ 2..value ]
unsigned count = CountEvenDivNatNum( i ); // узнаем сколко положительных четных делителлей у очередного числа из диапазона [ 2..value ]
if ( count > sought.countDivisor ) { // если число положительных четных делителей у очередного числа больше чем мы в прошлый раз запомнили
sought.value = i; // тогда запоминаем это число
sought.countDivisor = count; // и количество его делителей положительных четных делителей
}
}
return sought; // возвращаем результат
}
Объяснение кода листинга программы
- Структура для хранения числа и количества его четных положительных делителей называется Pair.
- Функция CountEvenDivNatNum() возвращает количество положительных четных делителей числа value.
- Функция MaxCountEvenDivNatNum() возвращает структуру, содержащую в своих полях:
- число из диапазона [ 2..value ] c максимальным количеством положительных четныx делителей,
- и это максимальное количество четных делителей.
- В функции main() происходит ввод числа n с клавиатуры, проверка корректности ввода и вывод результатов.
- Цикл в функции MaxCountEvenDivNatNum() перебирает все числа из диапазона [ 2..value ] и проверяет количество их положительных четных делителей.
- Если число положительных четных делителей у очередного числа больше чем мы в прошлый раз запомнили, то тогда запоминаем это число и количество его делителей положительных четных делителей.
- Результатом работы функции MaxCountEvenDivNatNum() является структура, содержащая в своих полях:
- искомое число с максимальным числом положительных четных делителей из диапазона [ 2..n ],
- и само количество этих положительных четных делителей.