PAT 1059

题目 ： Prime Factors

分值 ： 25
难度 ： 中等题
思路 ： 从 小数开始遍历 N的因数，是因数就用 N一直除到 除不尽为止，不用去判断素数不素数，
       因为你 一个非素数能够被 N当作因子的话 ，肯定在前面就已经 被除掉了 ，例如12 非
       素数因子 6 ，你在之前除 2 除 3 时就已经将这个非素数的因子全部剔除了吗，因此能
       够被除尽的只有可能是素数，因为只有素数没有办法在之前的遍历中被剔除因数。
       表述有点问题 总结来说：一个非素数 可以写成比他小的若干个 素数因子之积，我从小到
       大遍历因子并除尽，也就使得我之后不会遇到非素数作为因子，因为非素数的几个小因子都
       已经被我在之前的遍历中剔除干净了。
坑点 ： 输入小于 2是 0 或者 1 
评语 ： 水题两次AC

具体代码如下

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
#include <iostream>
using namespace std ;
int main() {
    int N ;
    cin >> N ;
    if(N <2)
    {
        cout <<N<<"="<<N ; 
        return 0 ; 
    }
    cout <<N <<"=";
    int flag = 0 ;
    for(int i =2 ; i<= N; i++)
    {
        int count = 0 ;
        while( N%i == 0 )
        {
            count ++ ;
            N /= i ;
        }
        if(count )
        {
            if(flag)
                cout <<"*" ;
            if(count>1)
                cout <<i<<"^"<<count ;
            else cout <<i ;
            flag =1 ;
        }
    }
    return 0 ; 
}