Ideone.com

download

copy

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
 
using namespace std;
 
class PrimeTable
{
public:
    PrimeTable(unsigned int count);
    ~PrimeTable() { delete[] table; }
    bool isPrime(long long n);
    int  next(int p);
private:
    bool * table;
    int  count;
};
 
PrimeTable::PrimeTable(unsigned int count)
:count(count)
{
    table = new bool[count+1];
    for(unsigned int i = 0; i <= count; ++i) table[i] = true;
    table[0] = table[1] = false;
    int last = sqrt(count)+1;
    for(int i = 2; i <= last; ++i)
    {
        if (table[i] == false) continue;
        for(unsigned int j = 2*i; j <= count; j += i) table[j] = false;
    }
}
 
 
bool PrimeTable::isPrime(long long N)
{
    if (N <= count) return table[N];
    int last = sqrt(N)+1;
    for(int i = 2; i <= last; i++)
    {
        if (table[i] == false) continue;
        if (N%i == 0) return false;
    }
    return true;
}
 
int PrimeTable::next(int p)
{
    if (p < count)
    {
        for(++p; p <= count; ++p)
            if (table[p]) return p;
    }
    return -1;
}
 
int CountDivs(unsigned int N)
{
    static PrimeTable t(10000);
    int count = 1;
    unsigned int M = N;
    while(N > 1)
    {
        for(int p = 2; p > 0 && t.isPrime(p) && p < sqrt(N) + 1; p = t.next(p))
        {
            int ex = 0;
            while(N%p == 0)
            {
                // cout << "Found " << p << endl;
                ++ex;
                N /= p;
            }
            count *= ex+1;
        }
        if (M == N) { count *= 2; N = 1; } // prime
        else M = N;
    }
    return count;
}
 
int main(int argc, const char * argv[])
{
    for(int N = 1; N < 1000; ++N)
        cout << setw(5) << N << ":  " << setw(4) << CountDivs(N) << endl;
}

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNtYXRoPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIFByaW1lVGFibGUKewpwdWJsaWM6CiAgICBQcmltZVRhYmxlKHVuc2lnbmVkIGludCBjb3VudCk7CiAgICB+UHJpbWVUYWJsZSgpIHsgZGVsZXRlW10gdGFibGU7IH0KICAgIGJvb2wgaXNQcmltZShsb25nIGxvbmcgbik7CiAgICBpbnQgIG5leHQoaW50IHApOwpwcml2YXRlOgogICAgYm9vbCAqIHRhYmxlOwogICAgaW50ICBjb3VudDsKfTsKClByaW1lVGFibGU6OlByaW1lVGFibGUodW5zaWduZWQgaW50IGNvdW50KQo6Y291bnQoY291bnQpCnsKICAgIHRhYmxlID0gbmV3IGJvb2xbY291bnQrMV07CiAgICBmb3IodW5zaWduZWQgaW50IGkgPSAwOyBpIDw9IGNvdW50OyArK2kpIHRhYmxlW2ldID0gdHJ1ZTsKICAgIHRhYmxlWzBdID0gdGFibGVbMV0gPSBmYWxzZTsKICAgIGludCBsYXN0ID0gc3FydChjb3VudCkrMTsKICAgIGZvcihpbnQgaSA9IDI7IGkgPD0gbGFzdDsgKytpKQogICAgewogICAgICAgIGlmICh0YWJsZVtpXSA9PSBmYWxzZSkgY29udGludWU7CiAgICAgICAgZm9yKHVuc2lnbmVkIGludCBqID0gMippOyBqIDw9IGNvdW50OyBqICs9IGkpIHRhYmxlW2pdID0gZmFsc2U7CiAgICB9Cn0KCgpib29sIFByaW1lVGFibGU6OmlzUHJpbWUobG9uZyBsb25nIE4pCnsKICAgIGlmIChOIDw9IGNvdW50KSByZXR1cm4gdGFibGVbTl07CiAgICBpbnQgbGFzdCA9IHNxcnQoTikrMTsKICAgIGZvcihpbnQgaSA9IDI7IGkgPD0gbGFzdDsgaSsrKQogICAgewogICAgICAgIGlmICh0YWJsZVtpXSA9PSBmYWxzZSkgY29udGludWU7CiAgICAgICAgaWYgKE4laSA9PSAwKSByZXR1cm4gZmFsc2U7CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKaW50IFByaW1lVGFibGU6Om5leHQoaW50IHApCnsKICAgIGlmIChwIDwgY291bnQpCiAgICB7CiAgICAgICAgZm9yKCsrcDsgcCA8PSBjb3VudDsgKytwKQogICAgICAgICAgICBpZiAodGFibGVbcF0pIHJldHVybiBwOwogICAgfQogICAgcmV0dXJuIC0xOwp9CgppbnQgQ291bnREaXZzKHVuc2lnbmVkIGludCBOKQp7CiAgICBzdGF0aWMgUHJpbWVUYWJsZSB0KDEwMDAwKTsKICAgIGludCBjb3VudCA9IDE7CiAgICB1bnNpZ25lZCBpbnQgTSA9IE47CiAgICB3aGlsZShOID4gMSkKICAgIHsKICAgICAgICBmb3IoaW50IHAgPSAyOyBwID4gMCAmJiB0LmlzUHJpbWUocCkgJiYgcCA8IHNxcnQoTikgKyAxOyBwID0gdC5uZXh0KHApKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGV4ID0gMDsKICAgICAgICAgICAgd2hpbGUoTiVwID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vIGNvdXQgPDwgIkZvdW5kICIgPDwgcCA8PCBlbmRsOwogICAgICAgICAgICAgICAgKytleDsKICAgICAgICAgICAgICAgIE4gLz0gcDsKICAgICAgICAgICAgfQogICAgICAgICAgICBjb3VudCAqPSBleCsxOwogICAgICAgIH0KICAgICAgICBpZiAoTSA9PSBOKSB7IGNvdW50ICo9IDI7IE4gPSAxOyB9IC8vIHByaW1lCiAgICAgICAgZWxzZSBNID0gTjsKICAgIH0KICAgIHJldHVybiBjb3VudDsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNvbnN0IGNoYXIgKiBhcmd2W10pCnsKICAgIGZvcihpbnQgTiA9IDE7IE4gPCAxMDAwOyArK04pCiAgICAgICAgY291dCA8PCBzZXR3KDUpIDw8IE4gPDwgIjogICIgPDwgc2V0dyg0KSA8PCBDb3VudERpdnMoTikgPDwgZW5kbDsKfQoK

Success #stdin #stdout 0s 3472KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/ZgcMoz

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language