【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number
【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number
Problem 12 Highly divisible triangular number
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be
. The first ten terms would be:
Let us list the factors of the first seven triangle numbers:
We can see that 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?
问题 12 高度可除的三角数
三角数由依次排列的自然数的和生成。所以第 7 个三角数是
。前十项是：
让我们列出前七个三角数的因数：
我们可以看到 28 是第一个有五个以上除数（因子）的三角数。 第一个有超过 500 个除数（因子）的三角数的值是多少？
思路分析
拿到题目，我们首先做的要理解清除题目含义，对于从未听过的陌生概念、术语（一般会举例说明），我们也要试着首先理解示例
这里解释下题目中的三角数是如何得出的，请看下表计算过程
第 x 个 | 三角数值 | 计算过程 |
|---|---|---|
1 | 1 | 1 |
2 | 3 | 1+2=3 |
3 | 6 | 1+2+3=6 |
4 | 10 | 1+2+3+4=10 |
5 | 15 | 1+2+3+4+5=15 |
6 | 21 | 1+2+3+4+5+6=21 |
7 | 28 | 1+2+3+4+5+6+7=28 |
… | … | … |
依然是老朋友，暴力枚举，从 开始依次枚举每个数字并判断它有多少个约数
当约数个数大于 500 时，退出循环并输出该值
代码实现
/*
* @Author: coder-jason
* @Date: 2022-04-19 20:58:43
* @LastEditTime: 2022-04-19 21:58:30
*/
#include <bits/stdc++.h>
using namespace std;
int factor(long long n) // 计算数字 num 因数个数 , 注意数据范围
{
int count = 0;
for (long long i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
if (i * i == n)
count++;
else
count += 2;
}
}
return count;
}
int main()
{
int num = 0;
for (long long i = 1;; i++)
{
num += i; // 枚举三角数 循环过程可参照末尾注解
if (factor(num) > 500) // 传值给 facto() 返回 num 因数个数
{
cout << num << endl; // 满足条件"第一个有超过 500 个因子"的三角数时,输出 num 值
break; // 循环结束
}
}
return 0;
} // num i num+=i; 过程演示
// 0 1
// 1 2
// 3 3
// 6 4
// 10 5答案：76576500
本题在完成三角数的枚举后，最重要的一步是如何判断一个数约数的个数
从基本思想不断优化，降低算法的时间复杂度，详请参考快速计算约数的个数——从基础到高级