Question

Число N, затем N целых чисел, которые нужно обработать. Наибольший простой общий делитель всех чисел (или 0, если такого нет). На си или алгоритм.

Answer 1

#include <stdio.h>
#include <math.h>

int isPrime(int x)
{
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) return 0;
}
return 1;
}

int main()
{

/* Ввод значений */
int n;
scanf("%d", &n);
int nums[n];
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}

/* Поиск минимального значения */
int min = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] < min) min = nums[i];
}

/* Поиск делителя */
int ret = 0;
int isDiv = 1;
for (int i = min; i > 1; i--) {
printf("test %d\n", i);
if (isPrime(i)) {
printf(" %d prime\n", i);
for (int j = 0; j < n; j++) {
if (nums[j] % i != 0) {
printf(" on pos %d not div %d\n", j, i);
isDiv = 0;
break;
}
}
if (isDiv) {
ret = i;
printf(" ret = %d, break\n", ret);
break;
}
else {
isDiv = 1;
}
}
}

printf("%d", ret);
return 0;
}

Answer 2

Алгоритм нахождения наибольшего простого общего делителя (НОД) для N целых чисел можно реализовать следующим образом:

1. Инициализируем переменную "НОД" значением первого числа из входных данных. 2. Для каждого следующего числа из входных данных: - Если это число равно 0, то НОД будет равен 0 и алгоритм завершается. - Если это число равно 1, то НОД не изменяется и переходим к следующему числу. - Иначе, находим НОД текущего числа и НОД, используя алгоритм Евклида. 3. Возвращаем полученное значение НОД.

Алгоритм Евклида для нахождения НОД двух чисел основан на следующем принципе:

- Если одно из чисел равно 0, то НОД равен другому числу. - Иначе, повторяем процесс с остатком от деления первого числа на второе число.

Си-код для реализации алгоритма:

#include

// Функция для нахождения наибольшего общего делителя двух чисел
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Функция для нахождения НОД N чисел
int findGCD(int arr[], int n) {
    int result = arr[0]; // Инициализируем НОД значением первого числа
    for (int i = 1; i < n; i++) {
        if (arr[i] == 0) {
            result = 0; // Если число равно 0, то НОД будет равен 0
            break;
        } else if (arr[i] == 1) {
            continue; // Если число равно 1, то НОД не изменяется
        } else {
            result = gcd(result, arr[i]); // Иначе, находим НОД текущего числа и НОД
        }
    }
    return result;
}

int main() {
    int n;
    printf("Введите число N: ");
    scanf("%d", &n);
    int arr[n];
    printf("Введите %d целых чисел: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int gcdResult = findGCD(arr, n);
    printf("Наибольший простой общий делитель всех чисел: %d\n", gcdResult);
    return 0;
}

Пример работы программы: ``` Введите число N: 5 Введите 5 целых чисел: 10 20 30 40 50 Наибольший простой общий делитель всех чисел: 10 ``` В этом примере, введены 5 чисел: 10, 20, 30, 40, 50. Наибольший простой общий делитель для этих чисел равен 10.