【欧拉计划第 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 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 1 + 2 + 3 + 4 + 5 + 6 + 7 = 281+2+3+4+5+6+7=28. The first ten terms would be:

1 , 3 , 6 , 10 , 15 , 21 , 28 , 36 , 45 , 55 , . . . 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...1,3,6,10,15,21,28,36,45,55,...

Let us list the factors of the first seven triangle numbers:

We can see that 28 2828 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 77 个三角数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 1 + 2 + 3 + 4 + 5 + 6 + 7 = 281+2+3+4+5+6+7=28。前十项是:

1 , 3 , 6 , 10 , 15 , 21 , 28 , 36 , 45 , 55 , . . . 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...1,3,6,10,15,21,28,36,45,55,...

让我们列出前七个三角数的因数:

我们可以看到 28 2828 是第一个有五个以上除数(因子)的三角数。

第一个有超过 500 500500 个除数(因子)的三角数的值是多少?

思路分析

拿到题目,我们首先做的要理解清除题目含义,对于从未听过的陌生概念、术语(一般会举例说明),我们也要试着首先理解示例

这里解释下题目中的三角数是如何得出的,请看下表计算过程

第 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

依然是老朋友,暴力枚举,从 1 11 开始依次枚举每个数字并判断它有多少个约数

当约数个数大于 500 500500 时,退出循环并输出该值

代码实现

/*
 * @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


本题在完成三角数的枚举后,最重要的一步是如何判断一个数约数的个数

从基本思想不断优化,降低算法的时间复杂度,详请参考快速计算约数的个数——从基础到高级



相关文章
Highly divisible triangular number( Problem 12)
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21,
1013 0
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
43 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
94 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
96 0
LeetCode 313. Super Ugly Number
|
算法
LeetCode 306. Additive Number
累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
122 0
LeetCode 306. Additive Number
|
算法
LeetCode 268. Missing Number
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
89 0
LeetCode 268. Missing Number