fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. unsigned int primes[] = {
  8.     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
  9.     61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
  10.     131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
  11.     197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
  12.     271, 277, 281, 283, 293, 307, 311, 313, 317
  13. };
  14.  
  15. inline unsigned long isqrt(unsigned long x)
  16. {
  17.     unsigned long x1, g0, g1;
  18.     if (x <= 1) return x;
  19.     int s = 1;
  20.     x1 = x - 1;
  21.     if (x1 > 0xFFFF)     { s = s +  8; x1 >>= 16; }
  22.     if (x1 > 0xFF)       { s = s +  4; x1 >>=  8; }
  23.     if (x1 > 0xF)        { s = s +  2; x1 >>=  4; }
  24.     if (x1 > 0x3)        { s = s +  1; }
  25.  
  26.     g0 = 1ll << s;
  27.     g1 = (g0 +(x>>s)) >> 1;
  28.     while( g1 < g0) {
  29.         g0 = g1;
  30.         g1 = (g0 + (x/g0)) >> 1;
  31.     }
  32.     return g0;
  33. }
  34.  
  35. int factors(unsigned long m)
  36. {
  37.     map<int,int> fs;
  38.     for(unsigned int i = 0; m > 1 && primes[i] <= isqrt(m);)
  39.     {
  40.         if (m%primes[i]) { ++i; continue; }
  41.         m /= primes[i];
  42.         fs[primes[i]]++;
  43.     }
  44.     if (m > 1) fs[m]++;
  45.  
  46.     int count = 1;
  47.     for(auto q: fs) count *= (q.second+1);
  48.     return count;
  49. }
  50.  
  51.  
  52. int main(int argc, const char * argv[])
  53. {
  54.     int total = 0, last = 1;
  55.  
  56.     for(unsigned long n = 2; n < 100000; ++n)
  57.     {
  58.         int count = factors(n);
  59.         if (last == count)
  60.         {
  61.             // cout << (n-1) << " vs " << n << " count = " << count << endl;
  62.             ++total;
  63.         }
  64.         else last = count;
  65.     }
  66.     cout << total;
  67. }
  68.  
  69.  
Success #stdin #stdout 0.07s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10585
https://ideone.com/QRI81U
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!