算法提高 質數的後代
時間限制:1.0s 記憶體限制:256.0MB
問題描述
在上一季裡,曾提到過質數的孤獨,其實從另一個角度看,無情隔膜它們的合數全是質數的後代,因為合數可以由質數相乘結合而得。
如果一個合數由兩個質數相乘而得,那麼我們就叫它是質數們的直接後代。現在,給你一系列自然數,判斷它們是否是質數的直接後代。
輸入格式
第一行一個正整數T,表示需要判斷的自然數數量
接下來T行,每行一個要判斷的自然數
輸出格式
共T行,依次對于輸入中給出的自然數,判斷是否為質數的直接後代,是則輸出Yes,否則輸出No
樣例輸入
4
3
4
6
12
樣例輸出
No
Yes
Yes
No
資料規模和約定
1<=T<=20
2<=要判斷的自然數<=105
import java.util.Scanner;
public class 質數的後代 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int[] data = new int[t];
for (int i = 0; i < t; i++) {
data[i] = sc.nextInt();
}
for (int i = 0; i < t; i++) {
find(data[i]);
}
}
private static void find(int i) {
// TODO Auto-generated method stub
int j;
for (j = 2; j < i; j++) {
if (i % j == 0) {
int m;
for (m = 2; m < j && j % m != 0; m++)
;
if (m == j) {
int d = i / j;
for (m = 2; m < d && d % m != 0; m++)
;
if (m == d) {
System.out.println("Yes");
break;
}
}
}
}
if (j == i) {
System.out.println("No");
}
}
}