A1059 Prime Factors (25分)

/*
题意：
1、给出一个long long
找出所有的质因子
注意：因子只有一个，个数是1， 不要打印1出来

解题：
1、先生成素数表，再进行质因子分解

learn && wrong:
1、质因子结构数组只要10就可以了
2、1需要特判的！
3、int范围内的正整数进行质因子分解，所以素数表只要10的5次方即可
4、不要再循环条件计算sqrt（n）
5、模板计算质因子，外层加了一个for就是了i < pnum && prime[i] <= sqr
同时注意质因子是从2开始的
6、判断质因子是从2开始的！
7、for里面有个特判，n=1直接break很好
8、输出乘号的格式，跟空格本质是一致的
*/

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

const int maxn = 100010;
bool isprime(int n) {
    if (n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2; i <= sqr; ++i) {    //！！！总是这里出错
        if (n % i == 0) return false;
    }
    return true;
}

int prime[maxn], pnum = 0;
void find_prime() {
    for (int i = 2; i < maxn; ++i) {
        if (isprime(i) == true) {
            prime[pnum++] = i;
        }
    }
}

struct factor {
    int x, cnt; //x为质因子，cnt为因子个数
} fac[10];

int main(int argc, char** argv) {
    find_prime();   //
    int n, num = 0; //num为不同质因子个数
    scanf("%d", &n);
    if (n == 1) printf("1=1");  //!!！特判1的情况
    else {
        printf("%d=", n);
        int sqr = (int)sqrt(1.0 * n);//n的根号
        //枚举根号以内的因子
        for (int i = 0; i < pnum && prime[i] <= sqr; ++i) {
            if (n % prime[i] == 0) {
                fac[num].x = prime[i];
                fac[num].cnt = 0;       //！！！是num为下标啊哥！
                while (n % prime[i] == 0) {
                    fac[num].cnt++;
                    n /= prime[i];
                }
                num++;
            }
            if (n == 1) break;  //即时推出循环，节省点时间
        }
        if (n != 1) {   //如果无法被根号n以内的质因子整除
            fac[num].x = n; //那么一定有一个大于sqr的因子
            fac[num++].cnt = 1;

        }
        //按格式输出结果
        for (int i = 0; i < num; ++i) {
            if (i > 0) printf("*");
            printf("%d", fac[i].x);
            if (fac[i].cnt > 1) {
                printf("^%d", fac[i].cnt);
            }
        }

    }
    return 0;
}