算法提高 质数的后代

时间:2021-07-06 11:01:31
/*
算法提高 质数的后代  

问题描述
  在上一季里,曾提到过质数的孤独,其实从另一个角度看,无情隔膜它们的合数全是质数的后代,因为合数可以由质数相乘结合而得。
  如果一个合数由两个质数相乘而得,那么我们就叫它是质数们的直接后代。现在,给你一系列自然数,判断它们是否是质数的直接后代。
输入格式
  第一行一个正整数T,表示需要判断的自然数数量
  接下来T行,每行一个要判断的自然数
输出格式
  共T行,依次对于输入中给出的自然数,判断是否为质数的直接后代,是则输出Yes,否则输出No
样例输入
4
3
4
6
12
样例输出
No
Yes
Yes
No
数据规模和约定
  1<=T<=20
  2<=要判断的自然数<=105

*/
import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        sc.close();
        Vector<Integer> v = new Vector<Integer>();
        for (int i = 2; i <= 100000; i++) {
            boolean flag = false;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag = true;
                    break;
                }

            }
            if (!flag)
                v.add(i);
        }
        for (int i = 0; i < a.length; i++)
            if (isH(a[i], v))
                System.out.println("Yes");
            else
                System.out.println("No");

    }

    static boolean isH(int k, Vector<Integer> v) {
        int m = v.size();
        for (int i = 0; i < m; i++) {
            if (v.get(i) >= k)
                return false;
            for (int j = 0; j < m; j++) {
                if (v.get(i) * v.get(j) > k)
                    break;
                else if (v.get(i) * v.get(j) == k)
                    return true;
            }

        }
        return false;
    }

}