题目179：连续正除数

欧拉计划

Consecutive positive divisors

Find the number of integers 1 < n < 10⁷, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

题目：

对于某些整数 n，n 和 n+1 有着相同个数的正除数（因子），比如 14 的因子有 1，2，7，14， 而 15 的有 1，3，5，15。

请找出 1 < n < 10⁷ 中，满足上述条件的 n 的个数。

guosl

应用一个数的因子个数的公式：（a1+1)...(an+1)其中n=p1^a1...pn^an是原数的素因数分解。而素因数分解可以通过筛法求的每个数的最小素因数来进行。
结果是：986262。时间可以控制在0.2秒左右。
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int MAX = 10000000;
int cnt[MAX];

int main(void)
{
  memset(cnt, 0, sizeof(cnt));
  int M = (int)sqrt((double)MAX);
  for (int i = 1; i <= M; ++i)//筛法求因子个数
  {
    int j = i * i;
    ++cnt[j];
    for (int j = i * i + i; j <= MAX; j += i)
      cnt[j] += 2;
  }
  int sum = 0;
  for (int i = 2; i <= MAX; ++i)
  {
    if (cnt[i] == cnt[i + 1])
      ++sum;
  }
  cout << sum << endl;
  return 0;
}