$n$ 很大的时候 `prime[i]` 和 `prime[n/i]` 总得爆一个
by SuperAlex4 @ 2024-03-24 23:09:58
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int prime[100000] = { 0 };
int main() {
for (int i = 2; i < 100000; i++) {
if (prime[i] == 0) {
for (int j = 2 * i; j < 100000; j += i)prime[j] = 1;
}
}
int n;
cin >> n;
for (int i = 2; i <=sqrt(n); i++) {
if (prime[i] == 0 &&n%i==0) {
cout << n/i;
break;
}
}
return 0;
}
```
不需要且不可以判断 `prime[n/i] == 0`，因为其可能 $\ge100000$。
by lcyxds @ 2024-04-08 21:29:49
别用埃氏筛选，如果是100000000会筛到时间超限的。
有个方法：
对于某个整数，从2枚举到它的平方根，如果能被其中任意一个数整除，则它不是质数（小于2的数都不是质数）
（求关注！！！！！）
by GeorgeCHN @ 2024-04-22 18:25:34