PTA甲级 1096Consecutive Factors (20分)-质因子分解

文章目录

• • 题目原文
  • 生词如下:
  • 题目大意:
  • 题目思路如下:COPY 柳神
  • 代码如下:

强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的CSDN博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

PS 今天也是充满希望的一天.

题目原文

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

Input Specification:

Each input file contains one test case, which gives the integer N (1<N<231).

Output Specification:

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*...*factor[k], where the factors are listed in increasing order, and 1 is NOT included.

Sample Input:

630

Sample Output:

3
5*6*7

生词如下:

factors 因素,分解

consecutive 连续的

题目大意:

就是给你一个数.

然后求出这个数的最长的连续因数之和.

如果有两个序列的长度是相等的,那么我们选择那个开头数最小的序列.

题目思路如下:COPY 柳神

[Update v2.0] 由github用户littlesevenmo提供的更高效的解法：
**不用算连续因子最多不会超过12个，也不需要三重循环，两重循环即可，直接去计算当前部分乘积能不能整除N
**分析：1、如果只有一个因子，那么这个数只能为1或者质数。因此我们主要去计算两个及以上因数的情况。
2、在有两个及以上的数连乘中，因数的最大上限为sqrt(N) + 1
3、因此思路就是，不断构造连乘，看连乘的积是否是N的因数，如果是，则看这部分连乘的数的个数是否比已记录的多。
4、用变量first记录连乘的第一个数字，这里我把它赋初值为0，如果在寻找N的因数过程中，first没有改变，那么就表明N是1或者是一个质数～

代码如下:

#include <iostream>
#include <cmath>
using namespace std;
long int num, temp;
int main() {
    cin >> num;
    int first = 0, len = 0, maxn = sqrt(num) + 1;
    for (int i = 2; i <= maxn; i++) {
        int j;
        temp = 1;
        for (j = i; j <= maxn; j++) {
            temp *= j;
            if (num % temp != 0) break;
        }
        if (j - i > len) {
            len = j - i;
            first = i;
        }
    }
    //就是first在2-sqrt(num)+1里面没有一个因数.这个数是素数
    if (first == 0) {
        cout << 1 << endl << num;
    }
    else {
        cout << len << endl;
        for (int i = 0; i < len; i++) {
            cout << first + i;
            if (i != len - 1) cout << '*';
        }
    }
    return 0;
}

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.