08-18 01:04 蚌埠学院 C++ 发布于上海
关注
美团笔试8.17
第一题想不明白为什么会报0。
思路：预处理1e5的素数，遍历素数集和中n的约数，直接输出。
数量级：1e6
#include
#include
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair
#define x first
#define y second
const int maxl = 1e5 + 7;
vector prime; // 9592个素数
bool flag[maxl];
// 预处理
void init() {
int n = 1e5;
for (int i = 2; i <= n; i++) {
if (!flag[i]) prime.push_back(i);
for (int p : prime) {
if (p * i > n) break;
flag[p * i] = 1;
if (i % p == 0) break;
}
}
}
void slove() {
int n;
cin >> n;
for (int p : prime) {
if (n % p == 0) { // 判断此素数是否是n的约数
cout << n / p << endl;
return;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
init();
while(t--) slove();
return 0;
}
思路：预处理1e5的素数，遍历素数集和中n的约数，直接输出。
数量级：1e6
#include
#include
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair
#define x first
#define y second
const int maxl = 1e5 + 7;
vector
bool flag[maxl];
// 预处理
void init() {
int n = 1e5;
for (int i = 2; i <= n; i++) {
if (!flag[i]) prime.push_back(i);
for (int p : prime) {
if (p * i > n) break;
flag[p * i] = 1;
if (i % p == 0) break;
}
}
}
void slove() {
int n;
cin >> n;
for (int p : prime) {
if (n % p == 0) { // 判断此素数是否是n的约数
cout << n / p << endl;
return;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
init();
while(t--) slove();
return 0;
}
全部评论
shuashuashua?
门头沟学院 C++
n是素数的情况下应该直接输出n本身，你输出的是1，题目要求m大于2
shinely1999
东南大学 无线通信工程师
多少分进面
相关推荐
昨天 22:04
复旦大学 电源工程师 
投递完美世界等公司10个岗位 > 点赞 评论 收藏
分享
