#include <iostream>
#include <iomanip>
#include <map>
using namespace std;
unsigned int primes[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
271, 277, 281, 283, 293, 307, 311, 313, 317
};
inline unsigned long isqrt(unsigned long x)
{
unsigned long x1, g0, g1;
if (x <= 1) return x;
int s = 1;
x1 = x - 1;
if (x1 > 0xFFFF) { s = s + 8; x1 >>= 16; }
if (x1 > 0xFF) { s = s + 4; x1 >>= 8; }
if (x1 > 0xF) { s = s + 2; x1 >>= 4; }
if (x1 > 0x3) { s = s + 1; }
g0 = 1ll << s;
g1 = (g0 +(x>>s)) >> 1;
while( g1 < g0) {
g0 = g1;
g1 = (g0 + (x/g0)) >> 1;
}
return g0;
}
int factors(unsigned long m)
{
map<int,int> fs;
for(unsigned int i = 0; m > 1 && primes[i] <= isqrt(m);)
{
if (m%primes[i]) { ++i; continue; }
m /= primes[i];
fs[primes[i]]++;
}
if (m > 1) fs[m]++;
int count = 1;
for(auto q: fs) count *= (q.second+1);
return count;
}
int main(int argc, const char * argv[])
{
int total = 0, last = 1;
for(unsigned long n = 2; n < 100000; ++n)
{
int count = factors(n);
if (last == count)
{
// cout << (n-1) << " vs " << n << " count = " << count << endl;
++total;
}
else last = count;
}
cout << total;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPG1hcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp1bnNpZ25lZCBpbnQgcHJpbWVzW10gPSB7CiAgICAyLCAzLCA1LCA3LCAxMSwgMTMsIDE3LCAxOSwgMjMsIDI5LCAzMSwgMzcsIDQxLCA0MywgNDcsIDUzLCA1OSwKICAgIDYxLCA2NywgNzEsIDczLCA3OSwgODMsIDg5LCA5NywgMTAxLCAxMDMsIDEwNywgMTA5LCAxMTMsIDEyNywKICAgIDEzMSwgMTM3LCAxMzksIDE0OSwgMTUxLCAxNTcsIDE2MywgMTY3LCAxNzMsIDE3OSwgMTgxLCAxOTEsIDE5MywKICAgIDE5NywgMTk5LCAyMTEsIDIyMywgMjI3LCAyMjksIDIzMywgMjM5LCAyNDEsIDI1MSwgMjU3LCAyNjMsIDI2OSwKICAgIDI3MSwgMjc3LCAyODEsIDI4MywgMjkzLCAzMDcsIDMxMSwgMzEzLCAzMTcKfTsKCmlubGluZSB1bnNpZ25lZCBsb25nIGlzcXJ0KHVuc2lnbmVkIGxvbmcgeCkKewogICAgdW5zaWduZWQgbG9uZyB4MSwgZzAsIGcxOwogICAgaWYgKHggPD0gMSkgcmV0dXJuIHg7CiAgICBpbnQgcyA9IDE7CiAgICB4MSA9IHggLSAxOwogICAgaWYgKHgxID4gMHhGRkZGKSAgICAgeyBzID0gcyArICA4OyB4MSA+Pj0gMTY7IH0KICAgIGlmICh4MSA+IDB4RkYpICAgICAgIHsgcyA9IHMgKyAgNDsgeDEgPj49ICA4OyB9CiAgICBpZiAoeDEgPiAweEYpICAgICAgICB7IHMgPSBzICsgIDI7IHgxID4+PSAgNDsgfQogICAgaWYgKHgxID4gMHgzKSAgICAgICAgeyBzID0gcyArICAxOyB9CgogICAgZzAgPSAxbGwgPDwgczsKICAgIGcxID0gKGcwICsoeD4+cykpID4+IDE7CiAgICB3aGlsZSggZzEgPCBnMCkgewogICAgICAgIGcwID0gZzE7CiAgICAgICAgZzEgPSAoZzAgKyAoeC9nMCkpID4+IDE7CiAgICB9CiAgICByZXR1cm4gZzA7Cn0KCmludCBmYWN0b3JzKHVuc2lnbmVkIGxvbmcgbSkKewogICAgbWFwPGludCxpbnQ+IGZzOwogICAgZm9yKHVuc2lnbmVkIGludCBpID0gMDsgbSA+IDEgJiYgcHJpbWVzW2ldIDw9IGlzcXJ0KG0pOykKICAgIHsKICAgICAgICBpZiAobSVwcmltZXNbaV0pIHsgKytpOyBjb250aW51ZTsgfQogICAgICAgIG0gLz0gcHJpbWVzW2ldOwogICAgICAgIGZzW3ByaW1lc1tpXV0rKzsKICAgIH0KICAgIGlmIChtID4gMSkgZnNbbV0rKzsKCiAgICBpbnQgY291bnQgPSAxOwogICAgZm9yKGF1dG8gcTogZnMpIGNvdW50ICo9IChxLnNlY29uZCsxKTsKICAgIHJldHVybiBjb3VudDsKfQoKCmludCBtYWluKGludCBhcmdjLCBjb25zdCBjaGFyICogYXJndltdKQp7CiAgICBpbnQgdG90YWwgPSAwLCBsYXN0ID0gMTsKCiAgICBmb3IodW5zaWduZWQgbG9uZyBuID0gMjsgbiA8IDEwMDAwMDsgKytuKQogICAgewogICAgICAgIGludCBjb3VudCA9IGZhY3RvcnMobik7CiAgICAgICAgaWYgKGxhc3QgPT0gY291bnQpCiAgICAgICAgewogICAgICAgICAgICAvLyBjb3V0IDw8IChuLTEpIDw8ICIgdnMgIiA8PCBuIDw8ICIgY291bnQgPSAiIDw8IGNvdW50IDw8IGVuZGw7CiAgICAgICAgICAgICsrdG90YWw7CiAgICAgICAgfQogICAgICAgIGVsc2UgbGFzdCA9IGNvdW50OwogICAgfQogICAgY291dCA8PCB0b3RhbDsKfQoK