PAT 1096

题目 ： Consecutive Factors

分值 ： 20
难度 ： 简单题
思路 ： 最长连续因数串
坑点 ： 输入的是素数注意一下.

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <math.h>
using namespace std ;
int main() {
    int N ;
    cin >> N ;
    bool flag =true ;
    for(int i = 2 ; i<sqrt(N)+1 ; i++)
        if(N%i==0)
        { flag = false ; break ;}
    if(flag) {cout << 1<<endl << N ; return 0;}
    int max = 0 ,index ;
    for(int i = 2 ; i< sqrt(N)+1 ;i++)
    {
        int count= 0 ;
        int temp = N ;
        int cur = i ;
        while(temp % cur == 0)
        {
            temp/=cur ;
            cur++ ;
            count ++ ;
        }
        if(count > max )
        {
            max = count ;
            index= i ;
        }
    }
    cout <<max <<endl ;
    for(int i = 0 ; i< max ; i++)
    {
        if(i)
            cout <<"*";
        cout << index +i ;
    }
}