题目179：连续正除数
Consecutive positive divisorsFind the number of integers 1 < n < 107, 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 < 107 中，满足上述条件的 n 的个数。
本帖最后由 guosl 于 2022-11-22 08:48 编辑
应用一个数的因子个数的公式：（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;
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;
for (int j = i * i + i; j <= MAX; j += i)
cnt += 2;
}
int sum = 0;
for (int i = 2; i <= MAX; ++i)
{
if (cnt == cnt)
++sum;
}
cout << sum << endl;
return 0;
}
页:
[1]