质因数分解
内容纲要
质因数分解
题目描述
已知正整数 $n$ 是两个不同的质数的乘积，试求出较大的那个质数。
输入格式
输入只有一行，包含一个正整数 $n$（$6<n<10^9$）。
输出格式
输出只有一行，包含一个正整数 $p$，即较大的那个质数。
样例 #1
样例输入 #1
21样例输出 #1
7Answer
找出所有质数因子：从最小的质数2开始，检查每个数是否是n的因子，即n能否被这个数整除。如果能，那么这个数就是n的一个质数因子。
判断是否为质数：在找到每个因子的时候，还需要判断这个因子是否为质数。实际上，如果按照从小到大的顺序找因子，那么每找到一个因子，它一定是质数，因为如果它不是质数，那么它的质数因子会在它之前就被找到，此时它就不会被识别为n的因子。
找到较大的质数：由于n是两个不同质数的乘积，一旦找到第一个质数因子，即可通过n除以这个质数因子得到另一个质数因子，比较这两个质数因子的大小即可找到较大的那个。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextInt();
long p = 0;
for (long i = 2; i <=n; i++) {
if (n%i==0){
p = n/i;
break;
}else {
p = n;
}
}
System.out.println(p);
}
}import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n=x/ln(x)
int nn = (int) ((Math.ceil(Math.log(n)*n))*1.3);
boolean[] x = new boolean[nn];
Arrays.fill(x, true);
for (int i = 2; i < nn; i++) {
if(x[i]){
for (int j = 2; i*j < nn; j++) {
x[i*j] = false;
}
}
}
int sum = 0;
for (int i = 2; i < nn; i++) {
if (x[i]){
sum++;
}
if (sum==n){
System.out.println(i);
break;
}
}
}
}