Решение задачи "Простые числа - 2 " с Acmp

Без пояснения   Просмотров: 23


Знаете ли вы, что такое простое число? Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Например, числа 2, 3, 5, 7, 11 являются простыми. А числа 4, 6, 10 – составными.

Требуется из заданного набора чисел выбрать одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).

Код

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int a)
{
    bool r = 1;
    for(int i = 2; i <= sqrt(a); ++i)
        if(!(a % i)){
            r = 0;
            break;
        }
    return r;
}
 
int numberofPrime(int a)
{
    int r = 0;
    for(int i = 2; i < a/2 + 1; ++i)
        if(!(a % i))
            if(isPrime(i))
                ++r;
    return r;
}
 
int main()
{
    int n,t;
    cin >> n;
    vector<int> a;
    for(int i = 0; i < n; ++i){
        cin >> t;
        a.push_back(t);
    }
    int mn = a.at(0);
    int mn_dev = numberofPrime(mn);
    for(int i = 1; i < n; ++i){
        t = numberofPrime(a.at(i));
        if(t > mn_dev){
            mn = a.at(i);
            mn_dev = t;
        }
        else
            if(t == mn_dev && a[i] < mn){
                mn = a[i];
                mn_dev = t;
            }
    }
    cout << mn;
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться