#27354: 2ms, 104KB 解法
hugochu712@gmail.com
(HugoChu)
學校
:
國立臺灣大學
編號 : 168241
來源 : [140.112.238.225]
最後登入時間 ：
2023-08-29 19:30:14
a010. 因數分解
| From: [1.160.64.21] |
發表日期
:
2021-09-26 21:26
# include <stdio.h>
int main()
{
// make prime list
int primeListSize = 10000;
int primeListSizeSqrt = 100;
bool primeList[primeListSize];
bool flipflop = true;
for (int i = 3; i < primeListSize; i++) // init odd with true, even with false, except 2
{
primeList[i] = flipflop;
flipflop = ~flipflop;
}
primeList[2] = true;
for (int i = 3; i < primeListSizeSqrt; i++) // 3~99 as multipiler
for (int j = i*i; j < primeListSize; j += i) // remove all multiple of multipiler
primeList[j] = false;
long int input;
scanf("%ld", &input);
// find answer
bool isFirst = true;
for (int i = 2; i < primeListSize; i++)
{
if (primeList[i] == true) // if this is prime
{
int repeatTimes = 0;
while (input % i == 0)
{
repeatTimes++;
input /= i;
}
if (repeatTimes > 0)
{
if (isFirst == false)
printf(" * ");
else
isFirst = false;
printf("%d", i);
if (repeatTimes > 1)
printf("^%d", repeatTimes);
}
}
}
if (input > 1)
{
if (isFirst == false)
printf(" * ");
printf("%ld", input);
}
return 0;
}
ZeroJudge Forum