Натуральные числа, не делящиеся ни на один из квадратов простых чисел [требует правки]

Да все просто. Принцип включений-исключений + предвычисленная таблица простых чисел. Тут я считаю те, которые делятся, соответственно, не делящиеся - надо вычесть из N...

Делящихся на 4 - N/4 (деление везде далее - только целочисленное!). На 9 - N/9. На 4 и 9 - N/(4*9), их надо вычесть. На 25 - N/25. Только на 25 - N/25-N/(4*25)-N/(9*25)+N/(4*9*25). Ну, и так далее - чем дальше, тем суммы-разности длиннее...

Для миллиарда кратных какому-то квадрату - 392072876.

#include <iostream>
#include <iomanip>
using namespace std;
int primes2[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
    ...
    31583, 31601, 31607
};
const int pCount = sizeof(primes2)/sizeof(primes2[0]);
long long getCount(unsigned int N, int n, long long a = -1)
{
    if (n == -1) { return N/a; }
    long long b = 0;
    if (abs(a*primes2[n]) > N) return 0;
    for(int m = -1; m < n; ++m)
    {
        b += getCount(N,m,-a*primes2[n]);
    }
    return b;
}
int main(int argc, const char * argv[])
{
    for(int i = 0; i < pCount; ++i) primes2[i] *= primes2[i];
    unsigned int N = 1000000000;
    long long count = 0;
    for(unsigned int i = 0; i < pCount; ++i)
    {
        count += getCount(N,i);
    }
    cout << count << endl;
}

Полный код тут: http://ideone.com/d9rLTr

Просчитанное этим методом и "в лоб" сравнение для 1000000 - тут: http://ideone.com/G1noXW