Question

Дано N чисел. Найти самое большое число, на которое делятся все N чисел.

Answer 1

#include <iostream>
using namespace std;

int main(){
    int max,k,n,nod,p;
    int ar[1000];
    cin>>n;
    for(int i=0;i<n;i++){
            cin>>ar[i];
            }
    max=ar[0];
    for(int i=1;i<n;i++){
             if(ar[i]>max){
                max=ar[i];
                   k=1;
                    nod=1;}
                   }
    while(k!=max){
                  k++;
                  p=0;
                   for(int i=0;i<n;i++){
                           if(ar[i]%k==0){
                                          p++;}}
                           if(p==n){
                                    nod=k;}
                                    }
                   cout<<"NOD="<<nod;
                   cin.get();
                   cin.get();
                  return 0;
                  }

Answer 2

Для того чтобы найти самое большое число, на которое делятся все N чисел, нужно найти наименьшее общее кратное (НОК) этих чисел. НОК - это наименьшее положительное число, которое делится на все заданные числа без остатка.

Существует несколько способов вычисления НОК, один из них - это разложение каждого числа на простые множители и вычисление произведения наибольших степеней всех простых множителей. Например, для чисел 6, 9, 15:

6 = 2 * 3 9 = 3 * 3 15 = 3 * 5

Наибольшая степень 2, содержащаяся в этих числах - это 2^1. Наибольшая степень 3 - 3^2. Наибольшая степень 5 - 5^1. Поэтому НОК для этих чисел равен 2^1 * 3^2 * 5^1 = 90.

Таким образом, чтобы найти самое большое число, на которое делятся все N чисел, нужно выполнить следующие шаги:

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

Пример кода на Python:

pythonCopy code
from collections import Counter
from functools import reduce
from math import gcd

def prime_factors(n):
    """Возвращает список простых множителей числа n"""
    factors = []
    d = 2
    while d * d <= n:
        while (n % d) == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

def max_divisor(numbers):
    """Находит самое большое число, на которое делятся все числа из списка"""
    # Разложение каждого числа на простые множители
    factors = [prime_factors(n) for n in numbers]
    # Нахождение наибольшей степени каждого простого множителя
    prime_counts = {}
    for factor_list in factors:
        factor_counts = dict(Counter(factor_list))
        for factor, count in factor_counts.items():
            if factor not in prime_counts or count > prime_counts[factor]:
                prime_counts[factor] = count
    # Вычисление произведения простых множителей, возведенных в соответствующие степени
    result = reduce(lambda a, b: a * b, [prime ** count for prime, count in prime_counts.items()], 1)
    return result

Пример использования: