yp11051231@yphs.tp.edu.tw
(910-36 楊宸)
學校
:
臺北市私立延平高級中學
編號 : 165190
來源 : [203.72.178.2]
最後登入時間 ：
2024-10-23 12:41:56
我用埃氏篩法建表，但 MLE ，求縮短記憶體容量!!
# include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// 建表 (埃氏篩法 )
vector<int> All;
vector<int> Prime;
for (int i=2; i<2147483648; i++){
All.push_back(i);
}
while (All.size() != 0){
int Num = All[0];
Prime.push_back(Num);
All.erase(All.begin());
for (int j=0; j<All.size(); j++){
if (All[j] % Num == 0)
All.erase(All.begin()+j);
else
continue;
}
}
int N;
while (cin >> N){
int Check = count(Prime.begin(),Prime.end(),N);
if (Check == 0)
cout << "非質數" << '\n';
else
cout << "質數" << '\n';
}
return 0;
}
for (int i=2; i<2147483648; i++){
All.push_back(i);
}
迴圈這裡overflow了，int沒那麼大，形成無限迴圈，在我的電腦上測試記憶體吃了8GB然後程式就被中止了...而且你這樣子用push_back應該會很慢
就算沒overflow，int大小是4位元，All會包含2147483646個int，總大小大約是8GB，而這題記憶體限制512MB，當然不夠用
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
for (int i=2; i<2147483648; i++){
All.push_back(i);
}
迴圈這裡overflow了，int沒那麼大，形成無限迴圈，在我的電腦上測試記憶體吃了8GB然後程式就被中止了...而且你這樣子用push_back應該會很慢
就算沒overflow，int大小是4位元，All會包含2147483646個int，總大小大約是8GB，而這題記憶體限制512MB，當然不夠用
怎麼測試用了多少記憶體 我都手算欸
for (int i=2; i<2147483648; i++){
All.push_back(i);
}
迴圈這裡overflow了，int沒那麼大，形成無限迴圈，在我的電腦上測試記憶體吃了8GB然後程式就被中止了...而且你這樣子用push_back應該會很慢
就算沒overflow，int大小是4位元，All會包含2147483646個int，總大小大約是8GB，而這題記憶體限制512MB，當然不夠用怎麼測試用了多少記憶體 我都手算欸
工作管理員
yp11051231@yphs.tp.edu.tw
(910-36 楊宸)
學校
:
臺北市私立延平高級中學
編號 : 165190
來源 : [203.72.178.2]
最後登入時間 ：
2024-10-23 12:41:56
for (int i=2; i<2147483648; i++){
All.push_back(i);
}
迴圈這裡overflow了，int沒那麼大，形成無限迴圈，在我的電腦上測試記憶體吃了8GB然後程式就被中止了...而且你這樣子用push_back應該會很慢
就算沒overflow，int大小是4位元，All會包含2147483646個int，總大小大約是8GB，而這題記憶體限制512MB，當然不夠用怎麼測試用了多少記憶體 我都手算欸
工作管理員
感謝各位大大，很抱歉我又丟出一個問題，MLE的問題是解決了，但現在TLE，可以幫幫我嗎?
=========================================================
# include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N){
int QAQ = sqrt(N);
// 建表 ( 埃氏篩法 )
vector<int> All = {};
vector<int> Prime = {};
for (int i=2; i<=QAQ; i++){
All.push_back(i);
}
while (All.size() != 0){
int Num = All[0];
Prime.push_back(Num);
All.erase(All.begin());
for (int j=0; j<All.size(); j++){
if (All[j] % Num == 0)
All.erase(All.begin()+j);
else
continue;
}
}
int Check = 0;
for (int i=0; i<Prime.size(); i++){
if (N % Prime[i] == 0){
cout << "非質數" << '\n';
Check = 1;
break;
}
else
continue;
}
if (Check == 0)
cout << "質數" << '\n';
}
return 0;
}
感謝各位大大，很抱歉我又丟出一個問題，MLE的問題是解決了，但現在TLE，可以幫幫我嗎?
=========================================================
# include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N){
int QAQ = sqrt(N);
// 建表 ( 埃氏篩法 )
vector All = {};
vector Prime = {};
for (int i=2; i<=QAQ; i++){
All.push_back(i);
}
while (All.size() != 0){
int Num = All[0];
Prime.push_back(Num);
All.erase(All.begin());
for (int j=0; j<All.size(); j++){
if (All[j] % Num == 0)
All.erase(All.begin()+j);
else
continue;
}
}
int Check = 0;
for (int i=0; i<Prime.size(); i++){
if (N % Prime[i] == 0){
cout << "非質數" << '\n';
Check = 1;
break;
}
else
continue;
}
if (Check == 0)
cout << "質數" << '\n';
}
return 0;
}
你這樣每一筆測資都要建表一次，應該要在while (cin >> N)迴圈外建表比較快