Spring RTS Engine

Code: Select all

priority_queue < long long int > getFactors(long long int k) {
    /*
    a fairly naive algorithm that returns a priority queue containing
    all the integer divisors that fit into some integer
    */
    priority_queue<long long int> q;
    q.push(1); //all nums are divisible by 1
    q.push(k); //all nums are divisible by themselves
    long long int max = (k/2)+1;//there are no numbers that divide by more than 1 half themselves
    for(int i = 2; i<max; i++) {
        if(k%i == 0){
            q.push(i);
            q.push(k/i);
            max = k/i;
        }
    }
    return q;
}

int unfriendlyNumbers(vector < long long int > a,long long int k) {
    //validity checks
    if (0 > k || k > 10000000000000) {return -1;}
    if (a.size() > 1000000) {return -1;}
    
    //functional code
    priority_queue<long long int> factors = getFactors(k);
    int count = 0;
    bool good = false;
    while (!factors.empty()) {
        long long int test = factors.top();
        factors.pop();
        good = true;
        for (vector<long long int>::iterator it = a.begin(); it != a.end(); ++it) {
            if (*it % test == 0) {
                good = false;
                break;
            }
        }
        if (good) {
            count++;
        }
    }
    int ans = count;
    return ans;
}