發表新討論
#29755: 題目的 n 範圍是 -231 到 231？


narutoooo1771@gmail.com (トンカツ)

d121. 00583 - Prime Factors -- UVa 583 | From: [140.138.234.136] | 發表日期: 2022-03-30 15:30

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

#29759: Re:題目的 n 範圍是 -231 到 231？


cges30901 (cges30901)

d121. 00583 - Prime Factors -- UVa 583 | From: [27.53.33.71] | 發表日期: 2022-03-30 20:22

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


應該是-231到231吧

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

#29775: Re:題目的 n 範圍是 -231 到 231？


narutoooo1771@gmail.com (トンカツ)

d121. 00583 - Prime Factors -- UVa 583 | From: [140.138.234.136] | 發表日期: 2022-03-31 08:24

#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 有時間的話請幫我感恩

#29779: Re:題目的 n 範圍是 -231 到 231？


cges30901 (cges30901)

d121. 00583 - Prime Factors -- UVa 583 | From: [39.10.135.162] | 發表日期: 2022-03-31 11:25
for (int i = 3; i <= n; i++)


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

#29783: Re:題目的 n 範圍是 -231 到 231？


narutoooo1771@gmail.com (トンカツ)

d121. 00583 - Prime Factors -- UVa 583 | From: [140.138.234.136] | 發表日期: 2022-03-31 15:08
#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 請大神指點
#29785: Re:題目的 n 範圍是 -231 到 231？


cges30901 (cges30901)

d121. 00583 - Prime Factors -- UVa 583 | From: [39.8.107.25] | 發表日期: 2022-03-31 16:29
#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的話它也是一個因數

 

ZeroJudge Forum