プログラミング問題#6:priority queue練習問題(C++プログラム設計9週目)


説明
正の整数aが正の整数bよりも優先されるという意味を定義する.
*aの素因数の数(自身を含まない)はbの素因数の数より多い.
*両者の素因数が等しい場合、数値が大きい方が優先度が高い.
最初の要素数が0のコンテナが与えられ、その後、10の要素が追加されます.追加するたびに、最も優先度の高い要素と最も低い要素が出力され、コンテナから削除されます.
入力
1行目:num(要素の追加回数num<=30)
次の10*num行は、行ごとに正の整数n(n<1000000)である.
しゅつりょく
10個の整数を入力するたびに、出力コンテナの中で最も優先度の高い要素と最も低い要素がスペース間隔で表示されます.
サンプル入力
1
10 7 66 4 5 30 91 100 8 9

サンプル出力
66 5

ヒントソースは他人のもので、その中で関数オブジェクトが使われていて、よく使われています.方法はとても良いソースです
#include <iostream>
#include <cmath>
#include <set>
using namespace std;

//          
bool isPrime(int iVal)
{
    for (int i = 2; i <= sqrt((float)iVal); i++)
    {
        if (iVal % i == 0)
            return false;
    }
    return true;
}

//           
int getFactor(int a)
{
    int sum = 0;
    int k = 0;
    for (int i = 2; i <= sqrt((float)a); i++)
    {
        if (a % i == 0)// a/i = k,   
        {
            k = a / i;
            if (i != k && isPrime(k))
                sum += 1;
            if (isPrime(i))
            {
                sum += 1;
            }
        }
    }
    return sum;
}

//    ,    
class Compare_Class_Up
{
public:
    bool operator()(const int& a, const int& b)
    {
        int sumA = 0, sumB = 0;
        sumA = getFactor(a);
        sumB = getFactor(b);
        if (sumA == sumB)
        {
            if (a < b)
            {
                return true;
            }
            else
                return false;
        }
        else if (sumA > sumB)
        {
            return false;
        }
        else
            return true;
    }
};


int main()
{
    set<int, Compare_Class_Up> queue;
    int n = 0;
    cin >> n;
    while (n--)
    {
        int num;
        for (int i = 0; i < 10; i++)
        {
            cin >> num;
            queue.insert(num);
        }

        int min = *(queue.begin());
        int max = *(queue.rbegin());
        queue.erase(max);
        queue.erase(min);
        cout << max << ' ' << min << endl;
    }
    return 0;
}