大神的世界

建立質數表

輸入數字

質數小到大，判別是否能整除輸入

若能，則不斷除，並記錄該數及次數

直到所餘數字的平方根 < 測試質數時

輸出

依次數判別輸出型態

因為最後不用輸出 * 

故分開輸出

#include <iostream>
#include <cstring>
#include <cmath>

#define MAX 1000
#define Pri_Max 170

using namespace std;

bool* bprime = new bool[MAX];
int  prime[Pri_Max];

void setPrime()
{
    memset(bprime, true, MAX);
    memset(prime, 0, Pri_Max*4);

    bprime[0] = bprime[1] = false;

    for(int i = 2, j = 0; i<MAX; i++)
    {
        if(bprime[i])
        {
            prime[j++] = i;
            for(int k = i; k<MAX; k+=i)
                bprime[k] = false;
        }
    }
    delete []bprime;
}

int main()
{
    setPrime();

    int num;
    int factor[15], exponent[15];
    int i, j;

    while(cin >> num)
    {
        for(i = 0, j = 0; prime[i] <= sqrt(num); i++)
        {
            //記錄次數與因數
            if(num%prime[i] == 0)
            {
                factor[j] = prime[i];
                exponent[j] = 0;

                while(num%prime[i] == 0)
                {
                    num /= prime[i];
                    exponent[j]++;
                }
                j++;
            }
        }

        if(num > 1)
        {
            factor[j] = num;
            exponent[j] = 1;
            j++;
        }

        for(i = 0; i<j-1; i++)
        {
            cout << factor[i];
            if(exponent[i] != 1)
                cout << '^' << exponent[i];
            cout << " * ";
        }
        cout << factor[j-1];
        if(exponent[j-1] != 1)
                cout << '^' << exponent[j-1];
        cout << endl;
    }
    
    return 0;
}