星空's Blog
星空's Blog
PAT-A1096 Consecutive Factors

原题

Consecutive Factors (20 分)

题解

给定 1 ~ 2147483647的数,在int的范围内
求因式的最长连续字串
这里需要注意特殊情况的处理
即所给数值为素数的情况,因式长度为1,因式为该数本身(题目指定1不算作因式)

代码

#include <iostream>
#include <cmath>
using namespace std;

int main(void) { 
   int n;
   cin >> n;
   int end = sqrt(n);
   int maxLength = 0;
   int index = 0;
   for (int i = 2;i <= end;i++) {
       int length = 0;
       int t = n;
       while (t && t % (i + length) == 0) {
           t = t / (i + length);
           length++;
       }
       if (length > maxLength) {
           index = i;
           maxLength = length;
       }
   }
   //素数
   if (maxLength == 0) {
       cout << 1 << endl;
       cout << n << endl;
       return 0;
   }
   //非素数
   cout << maxLength << endl;
   for (int i = 0;i < maxLength - 1;i++) {
       cout << index + i << "*";
   }
   cout << index + maxLength - 1 << endl;
   return 0;
}
所有文章禁止转载。
代码仅供参考
为了对抗广告机器人,首次留言将会被审核
首页      算法学习      PAT-A      PAT-A1096 Consecutive Factors

星空

文章作者

发表评论

textsms
account_circle
email

星空's Blog

PAT-A1096 Consecutive Factors
原题 Consecutive Factors (20 分) 题解 给定 1 ~ 2147483647的数,在int的范围内 求因式的最长连续字串 这里需要注意特殊情况的处理 即所给数值为素数的情况,因式长度为1,因式为该数本…
扫描二维码继续阅读
2019-08-20