#include<stdio.h>
#include<stdlib.h>
int main(void){
int i,x;
int y=2;
while(scanf("%d",&x)!=EOF){
while(x>1){
int n=0;
while(x%y==0){
n++;
x=x/y;
}
if(n>1&&x==1){
printf("%d^%d\n",y,n);
break;
}
else if(n>1){
printf("%d^%d * ",y,n);
y++;
}
else if(n==1&&x==1){
printf("%d\n",y);
break;
}
else if(n==1){
printf("%d * ",y);
}
y++;
}
}
}
這是我寫的程式內容
可以請大家幫我看看怎麼改才不會TLE嗎?
#include
#include
int main(void){
int i,x;
int y=2;
while(scanf("%d",&x)!=EOF){
while(x>1){
int n=0;
while(x%y==0){
n++;
x=x/y;
}
if(n>1&&x==1){
printf("%d^%d\n",y,n);
break;
}
else if(n>1){
printf("%d^%d * ",y,n);
y++;
}
else if(n==1&&x==1){
printf("%d\n",y);
break;
}
else if(n==1){
printf("%d * ",y);
}
y++;
}
}
}
這是我寫的程式內容
可以請大家幫我看看怎麼改才不會TLE嗎?
First : 你的 y =2 要每次輸入完都初始化
Second : else if(n > 1) 那邊 要continue 要不然y會++兩次
0u0
#include<stdio.h>
#include<stdlib.h>
int main(void){
int i,x;
while(scanf("%d",&x)!=EOF){
int y=2;
while(x>1){
int n=0;
while(x%y==0){
n++;
x=x/y;
}
if(n>1&&x==1){
printf("%d^%d\n",y,n);
break;
}
else if(n>1){
printf("%d^%d * ",y,n);
y++;
continue;
}
else if(n==1&&x==1){
printf("%d\n",y);
break;
}
else if(n==1){
printf("%d * ",y);
}
y++;
}
}
}
請建立質數表 + 善用開根號 加快速度
以下程式碼拿到 AC (0ms, 300KB)
但我不知道怎麼縮小記憶體用量 ...
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int prime_number[168];
int total, a, b, c, input;
bool state;
prime_number[0] = 2;
prime_number[1] = 3;
total = 2;
//建立質數表
for(a = 5; a <= 1000; a += 2)
{
for(b = sqrt(a), c = 1, state = true; c < total && prime_number[c] <= b; c++)
{
if(a % prime_number[c] == 0)
{
state = false;
break;
}
}
if(state)
{
prime_number[total] = a;
total++;
}
}
//主程式
while(cin >> input)
{
for(a = 0, b = sqrt(input), state = false; prime_number[a] <= b; a++, b = sqrt(input))
{
if(input % prime_number[a] == 0)
{
for(c = 1, input /= prime_number[a]; input % prime_number[a] == 0; c++, input /= prime_number[a]);
if(state) cout << " * ";
else state = true;
if(c == 1) cout << prime_number[a];
else cout << prime_number[a] << "^" << c;
}
}
if(!state)
{
cout << input << endl;
}
else
{
if(input != 1)
{
cout << " * " << input << endl;
}
else
{
cout << endl;
}
}
}
return 0;
}