(Relax 数论1.10)POJ 1365 Prime Land(质因数分解) - c++编程基础

题目大意：给出n的质因数分解式,求n-1的质因数的分解式。比如第二组sample，就是5^1*2^1=10, 求10-1即9的质因数分解，从大到小输出，即3^2.本来很简单的嘿，直接最暴力最裸的就行了。

#include   
#include   
#include   
#include   
#include   
  
/** 
 * 2 2 3 17 
 2 2 3 29 

 2 2 5 37 
 */  
using namespace std;  
  
const int maxn = 100002;  
  
int su[100002];  
bool u[100002];  
int num = 0;  
  
void prepare() {//欧拉筛法产生素数表...  
    int i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= 100002; ++i) {  
        if (u[i]) {  
            su[++num] = i;  
        }  
  
        for (j = 1; j <= num; ++j) {  
            if (i * su[j] > 100002) {  
                break;  
            }  
  
            u[i * su[j]] = false;  
  
            if (i % su[j] == 0) {  
                break;  
            }  
        }  
    }  
}  
//------------------------  
int path[maxn];//底  
int po[maxn];//指数  
int cnt;//用到了多少个质因数  
  
void solve(int n) {//对n进行质因数分解  
  
    cnt = 0;  
    int i;  
    for (i = 1; su[i] <= n && n != 1; ++i) {  
  
        int ct = 0;  
        while (n % su[i] == 0) {  
            ct++;  
            n /= su[i];  
        }  
  
        if (ct != 0) {  
            path[cnt] = su[i];  
            po[cnt++] = ct;  
        }  
    }  
  
    for (i = cnt - 1; i >




= 0; --i) {//输出分解完的式子  
        if (i != 0) {  
            printf("%d %d ", path[i], po[i]);  
        } else {  
            printf("%d %d\n", path[i], po[i]);  
        }  
    }  
}  
  
int main() {  
  
    /** 
     * ****特别要注意这种格式数据的处理... 
     * 17 1 
       5 1 2 1 
       509 1 59 1 
       0 
     */  
    prepare();  
  
    int a, b, num1;  
    char ch;  
    while (scanf("%d", &a) != EOF, a) {  
        scanf("%d%c", &b, &ch);  
        num1 = 1;  
        num1 *= (int) pow(a * 1.0, b * 1.0);  
  
        while (ch != '\n') {  
            scanf("%d%d%c", &a, &b, &ch);  
            num1 *= pow(a + 0.0, b);//**这里需要注意一下  
        }  
  
        solve(num1 - 1);  
    }  
  
    return 0;  
}