Unfriendly numbers c++

Question

There is a problem on interviewstreet called UnfriendlyNumbers. The problem goes like this -

There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers. Sample Input: 8 16 2 5 7 4 3 8 3 18 Sample Output: 1

All the testcases that I can imagine execute correctly, but for some reason, the website deems it incorrect for a set of testcases. Do you guys see any errors in the code/logic?

void get_factors(unsigned long n, vector<unsigned long> &factors)
{
    unsigned long sqrt = pow(n, 0.5);
    for (unsigned long i = 1; i < sqrt; i++) {
        if (n%i == 0) {
            factors.push_back(i);
            factors.push_back(n/i);
        }
    }
    if (n%sqrt == 0) {
        factors.push_back(sqrt);
    }
}


int
main(int argc, char *argv[])
{
    unsigned int n; 
    unsigned long k, j;
    cin >> n >> k;

    if (n == 0 || k == 0) {
        cout << 0 << endl;
        return 0;
    }

    set<unsigned long> unfriendly;
    for (int i = 0; i < n; i++) {
        cin >> j;
        unfriendly.insert(j);
    }

    vector<unsigned long> factors;
    get_factors(k, factors);

    unsigned int count = factors.size();
    for (int i = 0; i < factors.size(); i++) {
        for (set<unsigned long>::iterator it = unfriendly.lower_bound(factors[i]); 
             it !=  unfriendly.end();
             it++)
        {
            if (*it % factors[i] == 0) {
                count--;
                break;
            }
        }
    }
    cout << count;
}

Answer 1

Get the common divisors between the unfriendly numbers and the friendly number K using GCD. O(N)

Then get the divisors of K in O(sqrt(K)).

Loop the cmn_div and div of k, to get the answer in O(N*sqrt(K))

Answer 2

Your get_factors is incorrect. For numbers like 30 or 35, some divisors are omitted.

sqrt is the largest integer not exceeding the square root, but when n == sqrt*(sqrt+1) or n == sqrt*(sqrt+2), you don't record sqrt+1 resp. sqrt+2 as divisors.

Also, there is the possibility that

unsigned long sqrt = pow(n, 0.5);

can yield a wrong result if n is sufficiently large, better adjust it

while(sqrt > n/sqrt) --sqrt;
while(sqrt+1 <= n/(sqrt+1)) ++sqrt;

And, it may be that unsigned long isn't large enough, for safety use unsigned long long.

Apart from that, the only thing I see that could fail is if any of the numbers is 0.

    for (set<unsigned long>::iterator it = unfriendly.lower_bound(factors[i]); 
         it !=  unfriendly.end();
         it++)

will fail if an unfriendly number is 0; and if the friendly number is 0, all bets are off (the answer is then 0 if any unfriendly number is 0, infinity otherwise).