ZeroJudge [a010: 因數分解] by Go-Ice

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
void listPrime();
void resetArray();

int main(){
    int input;          /* input number(1 < n <= 1000000)*/
    int index;          /* array index */
    int factorAmount;   /* amount of factors */
    int prime[169];     /* list of prime numbers */
    int power[169];     /* factors' power (169 prime number between 1 to 1000) */

    listPrime( &prime[0] );

    while ( scanf("%d", &input)==1 ){
        /* reset variables */
        resetArray( &power[0] );
        factorAmount = 0;

        for ( index=1 ; index<169 ; index++ ){
            if ( input%prime[index] == 0 ){
                power[index]++;
                input /= prime[index];
                index = 0;
            }

            if ( input ==  1 )
                break;
        } /* END for */

        for ( index=1 ; index<169 ; index++ ){
            if ( power[index] == 1 ){
                if ( factorAmount >= 1 )
                    printf(" * ");

                printf("%d", prime[index]);
                factorAmount++;
            } /* END outer if */

            else if ( power[index] > 1 ){
                if ( factorAmount >= 1 )
                    printf(" * ");

                printf("%d^%d", prime[index], power[index]);
                factorAmount++;
            } /* END else if */
        } /* END printer for */

        if ( input != 1 ){
            if ( factorAmount >= 1 )
                printf(" * ");

            printf("%d", input);
        }

        printf("\n");
    } /* END outer while */

    system("PAUSE");
    return 0;
} /* END main */

void listPrime( int *array ){
    int number;
    int divisor;
    int isPrime;        /* flag of prime number */
    int sqrtAns;        /* answer of sqrt(Number) */

    /* set first 3 prime number */
    *array++ = 1;
    *array++ = 2;
    *array++ = 3;

    /* make a list of prime numbers(1<n<1000) */
    for ( number=5 ; number<=1000 ; number+=2 ){
        isPrime = 1;    /* reset flag */

        sqrtAns = sqrt((double)number);
        for ( divisor=3 ; divisor<=sqrtAns ; divisor+=2 ){
            if( number%divisor == 0 ){
                isPrime = 0;
                break;
            }
        } /* END inner for*/

        if ( isPrime )
            *array++ = number;
    } /* END outer for */
} /* END void listPrime() */

void resetArray( int *array ){
    int cnt;
    for ( cnt=0 ; cnt<169 ; cnt++ )
        *array++ = 0;
} /* END void resetArray() */