---

那我建表為什麼會錯？一開始沒建表還會 TLE 嗚嗚

 

---

那我建表為什麼會錯？一開始沒建表還會 TLE 嗚嗚

應該是-2³¹到2³¹吧

這題時間有3秒，我覺得很夠用了，不需要建表，一個一個檢查是否是因數就能AC了

 

---

#include <iostream>

using namespace std;

 

int main()

{

int n;

while (cin >> n && n != 0)

{

cout << n << " = ";

 

if (n < 0)

{

cout << "-1 x ";

n *= -1;

}

 

if (n % 2 == 0)

{

while (n % 2 == 0)

{

n /= 2;

cout << 2;

 

if (n != 1)

{

cout << " x ";

}

}

}

 

for (int i = 3; i <= n; i++)

{

if (n % i == 0)

{

while (n % i == 0)

{

n /= i;

cout << i;

 

if (n != 1)

{

cout << " x ";

}

}

}

}

 

cout << '\n';

}

 

return 0;

}

 

仍然是 TLE 有時間的話請幫我感恩

 

---

for (int i = 3; i <= n; i++)

不需要算到n，只要到平方根就好了，可以用內建的sqrt()

 

---

#include <iostream>

#include <cmath>

using namespace std;

 

bool prime(long int n);

 

int main()

{

long int n;

while (cin >> n && n != 0)

{

cout << n << " = ";

 

if (n < 0)

{

cout << "-1 x ";

n *= -1;

}

 

if (prime(n))

{

cout << n << '\n';

}

else

{

if (n % 2 == 0)

{

while (n % 2 == 0)

{

n /= 2;

cout << 2;

 

if (n != 1)

cout << " x ";

else

cout << '\n';

}

}

 

for (int i = 3; i <= n; i+=2)

{

while (n % i == 0)

{

n /= i;

cout << i;

 

if (n != 1)

cout << " x ";

else

cout << '\n';

}

}

}

}

 

return 0;

}

 

bool prime(long int n)

{

if (n == 2)

return true;

else if (n % 2 == 0)

return false;

else

{

for (int i = 3; i <= int(sqrt(n)); i+=2)

{

if (n % i == 0)

return false;

}

return true;

}

}

我打算先判斷質數，剩下的再解決，雖然還是沒有用你說的 sqrt() 因為我不清楚怎麼寫比較快

不過仍然是超時Q_Q 請大神指點

 

---

#include

#include

using namespace std;

 

bool prime(long int n);

 

int main()

{

long int n;

while (cin >> n && n != 0)

{

cout << n << " = ";

 

if (n < 0)

{

cout << "-1 x ";

n *= -1;

}

 

if (prime(n))

{

cout << n << '\n';

}

else

{

if (n % 2 == 0)

{

while (n % 2 == 0)

{

n /= 2;

cout << 2;

 

if (n != 1)

cout << " x ";

else

cout << '\n';

}

}

 

for (int i = 3; i <= n; i+=2)

{

while (n % i == 0)

{

n /= i;

cout << i;

 

if (n != 1)

cout << " x ";

else

cout << '\n';

}

}

}

}

 

return 0;

}

 

bool prime(long int n)

{

if (n == 2)

return true;

else if (n % 2 == 0)

return false;

else

{

for (int i = 3; i <= int(sqrt(n)); i+=2)

{

if (n % i == 0)

return false;

}

return true;

}

}

我打算先判斷質數，剩下的再解決，雖然還是沒有用你說的 sqrt() 因為我不清楚怎麼寫比較快

不過仍然是超時Q_Q 請大神指點

你這樣判斷質數不會比較快，可以設一個變數s為sqrt(n)，把for迴圈的i<=n改成i<=s，然後一旦找到因數，就重新計算s=sqrt(n)，這樣迴圈跑的次數就會減少很多。最後迴圈跑完以後如果n不是1的話它也是一個因數