美团笔试8.17
第一题想不明白为什么会报0。
思路:预处理1e5的素数,遍历素数集和中n的约数,直接输出。
数量级:1e6
#include<bits/stdc++.h>
#include <vector>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e5 + 7;
vector<int> 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<bits/stdc++.h>
#include <vector>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e5 + 7;
vector<int> 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;
}
全部评论
n是素数的情况下应该直接输出n本身,你输出的是1,题目要求m大于2
多少分进面
相关推荐
点赞 评论 收藏
分享