a010.
因數分解
| From: [219.77.25.250] |
發表日期
:
2010-04-16 19:26
#include <iostream>
using namespace std;
int is_prime(int number)
{
if ( number == 2 || number == 3) return 1;
else if (number == 1 || number % 2 == 0) return 0;
for (int x = 3 ; x*x < number ; x+=2)
if (number % x == 0) return 0;
return 1;
}
int main()
{
int n = 0;
while ( cin >> n ){
int *prime_factor = new int [n/2];
int input = n;
int index = 0;
for (int test_value = 2 ; test_value <= n/2 ; test_value ++)
{
while ( is_prime(test_value) )
{
if (input % test_value == 0)
{
prime_factor[index] = test_value;
input /= test_value;
index++;
}
else
break;
}
}
if (index == 0) prime_factor[index++] = n;
for (int counter = 0; counter < index ; counter ++)
{
static int count = 0;
if ( prime_factor[counter] == prime_factor[counter+1])
count++;
else if ( (prime_factor[counter] != prime_factor[counter+1]) && count > 0 )
{
cout << prime_factor[counter] << "^" << count+1 << (counter+1 == index ? "" : " * ") ;
count = 0;
}
else if (prime_factor[counter] != prime_factor[counter+1])
cout << prime_factor[counter] << ( counter+1 == index ? "" : " * " );
}
cout << endl;
delete [] prime_factor;
}
return 0;
}