Как найти нок массива

Этого, к счастью, уже не требуется, так как нормальное решение уже было предложено уважаемым Fixer_84 в посте №3. Я бы несколько оптимизировал в нем нахождение НОД (см. мой пост №4), но на эту тему на форуме имеется вполне достаточное количество публикаций.

Да, я в курсах. Если вам хочется для решения простой арифметической задачки, решающейся за 0.001 сек, применить метод, который решает ее за 3 сек — ваше право.
Такие методы еще носят общее название БрутФорс (грубая сила). И все усилия программистов и математиков предыдущего и текущего столетий были направлены на то, чтобы сделать эти методы понежнее.

Добавлено через 4 минуты

В самом деле это условие выполнить очень несложно. Ибо именно таковыми знаниями я и обладаю (не считая кой-каких заморочек, которые к делу не относятся). Тут дело не в знании языков. А в алгоритмах. В соображалке, короче.

Задача:

Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива.

Решение:

Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел. Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, ... аN) равен НОК(НОК(НОК(А1, А2), А3)..., АN). Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут.

Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):

#include <stdio.h>
#include <stdlib.h>

void read_array(int n, int** values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = ", i);
        scanf("%d", &((*values)[i]));
    }
}

void print_array(int n, int* values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = %dn", i, values[i]);
    }
}

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int gcd(int a, int b) {
    if (a < b) {
        swap(&a, &b);
    }
    while (a % b != 0) {
        a = a % b;
        swap(&a, &b);
    }
    return b;
}

int gcd_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int gcd_value = gcd(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        gcd_value = gcd(gcd_value, values[i]);
    }
    return gcd_value;
}

int lcm(int a, int b) {
    return (a*b)/gcd(a, b);
}

int lcm_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int lcm_value = lcm(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        lcm_value = lcm(lcm_value, values[i]);
    }
    return lcm_value;
}

int main() {
    int n;
    int *values;
    
    printf("n: ");
    scanf("%d", &n);
    
    values = malloc(sizeof(int) * n);
    
    read_array(n, &values);
    
    printf("lcm: %d", lcm_n(n, values));
    
    free(values);
    return 0;
}

Вот следующие куски кода изображаю одну из реализаций алгоритма. Смысл написанного в том что все числа как бы параллельно разлаживаются в последовательность. Сначала все числа делим на 2. Если число делиться без остатка, то результат деления записывается на место занимаемое число в таблице. Если не делится, то просто пропускается. Если при проходе массива произошло хотя бы одно деление то текущее значение НОК умножается на 2 и текущим простым число остается 2, итерация повторяется. Если делений не было, то пора заменить текущее простое число на следующее. Если в таблице не осталось чисел больше 1 то пора выводить число HOK и прекращать обработку.

int table_pn [] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149};

// функция возвращает следующее простое число стоящее за переданным в параметре
int get_next_pn(int x)
{
	int result = 0; // елемент не найден
	for (int i = 0; i < sizeof(table_pn) / sizeof(int); i++)
	{
		if (x < table_pn[i])
		{
			result = table_pn[i];
			break;
		}
	}
	return result;
}

...

	int table_a [5] = {5, 6, 13, 8, 22}; // массив чисел

	int pn = 2; // стартовое простое число
	int nok = 1; // инициализируем переменную под хранение НОК и именно еденицей
	
	int a = 1; // есть что делить? 1 - да, 0 - нет (1 нужна, что бы первый раз зайти в цикл)
	while (a)
	{
		// начинаем итерацию
		a = 0;  // в начале итерации считаем что массив не содержит числа которые можно поделить на простое число
		int next_pn = 1;  // в начале итерации считаем что неоьходимо получить следующее простое число
		for (int i = 0; i < sizeof(table_a) / sizeof(int); i++) // обрабатываем каждый элемент массива
		{
			if (table_a[i] > 1) // проверяем, можно ли число разделить на простое число
			{
				if ((table_a[i] >= pn) && (table_a[i] % pn == 0.0f)) // проверяем число на деление без остатка
				{
					table_a[i] = (int) (table_a[i] / pn); // зарисываем результат деления в таблицу замещая число
					next_pn = 0; // отмечам, что ненадо менять простое число
				}
				if (table_a[i] > 1)
				{
					// если результат в таблице все еще можно делить, то нужно отметить необходимость продолжения итераций
					a = 1;
				}
			}
		}
		if (next_pn)
		{
			// делений в цикле не было значит пора менять простое число на большее
			pn = get_next_pn(pn); // получам следующее простое число
			if (!pn)
			{
				// если получить простое число не получилось, значит их мало в таблице и необходимо сообщить об ошибке
				// nok ставим в 1 и на ввыходе программа сама будет знать что посчитать не удалось
				nok = 1;
				break;
			}
		} else
		{
			// иначе к текущее значение nok умножим на текущее простое число
			nok *= pn;
		}
	}

	if (nok > 1)
	{
		printf("NOK = %dn", nok);
	} else
	{
		printf("NOK ne najden!!!n");
	}