题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.*;
class Main{
public static void main(String[] args) {
// 因为题目说是两个质数相乘 得到n 如果找到一个质数 i使的n % i == 0 那么必然是唯一解 因为两个质数 必然是唯一不变无法拆分组合
//如果遍历sqrt(n) 的数 但每个数要sqrt(sqrt(n))的时间判定是否是质数 总时间复杂度n ^ 3/ 4 然后
// 如果先用count prim的方法找出2 - sqrt(n)之间的 筛选出质数 这个时间是sqrt(n) * log(sqrt(n)) 之后遍历花费sqrt(n)
// (logn + 1) n ^ 1 / 2 感觉可能差不多时间复杂度
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = (int) Math.sqrt(n);
boolean[] isPrime = new boolean[x + 1];
Arrays.fill(isPrime, true);
for (int i = 4; i <= x; i += 2) isPrime[i] = false;
for (int i = 3; i * i <= x; i += 2) {
if (isPrime[i]) {
for (int j = i * i; j <= x; j += 2 * i) {
isPrime[j] = false; // 这里是isPrime[j] 之前写成了isPrime[i] 导致错误
}
}
}
int res = 0;
// sqrt(n)
for (int i = 2; i <= x; i++) {
if (isPrime[i] && n % i == 0) {
res = Math.max(i, n / i);
}
}
System.out.print(res);
}
}