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


Простые множители


Сформировать массив простых множителей заданного числа. Простые множители числа -простые числа, произведение которых дает заданное число, например: 72 = 2*2*2*3*3.

Шаг 1: Исходные данные и результат -формальные параметры функции.


void calc(int val, int A[], int n) { ... }
val -Заданное число
A - Масссив простых множителей
n - Размерность массива

Шаг 2: Форма представления результата. Последовательность простых множителей в массиве А ограничена значением 0. Основной цикл получения множителей состоит в выделении очередного множителя из val и запоминания его.


void calc(int val, int A[], int n)
{
int i; // Количество множителей


int m; // Значение множителя


for (i=0; не кончился массив и есть множители; i++)
{
// Получить значение множителя m


A[i] = m;
}
A[i]=0;
}

Шаг 3. Получение очередного простого множителя. Простой множитель -минимальное простое число, на которое исходное делится без остатка. Если оно найдено, то в следующем шаге нужно использовать частное от деления исходного числа на множитель, чтобы искать следующий, то есть val = val / m; Последний множитель даст переменной val значение 1.


void calc(int val, int A[], int n)
{
int m,i;
for (i=0; i&#60n-1 &#38&#38 val !=1; i++)
{
// Получить минимальное простое число m, нацело делящее val


val /= m; A[i] = m;
}
A[i] = 0;
}

Шаг 4: Для поиска минимального m, нацело делящего val, в цикле подряд проверяются все m, начиная с 2, до тех пор, пока остаток от деления не станет равным 0. Окончательный вариант:


//------------------------------------------------------bk32-01.cpp


//------Простые множители числа


void calc(int val, int A[], int n)
{
int m,i;
for (i=0; i&#60n-1 &#38&#38 val !=1; i++)
{
for (m=2; val % m !=0; m++);
val /= m; A[i] = m;
}
A[i] = 0;
}





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