AcWing——4268. 性感素

4268. 性感素

一、测试链接

点我跳转

二、题目分析

难度：简单
时/空限制：0.4s / 64MB
来源：PAT甲级真题1156
算法标签：枚举质数试除法

三、题目描述

“性感素数 ”是指形如 $(p,p+6)$ 这样的一对素数。

之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。

现给定一个整数，请你判断其是否为一个性感素数。

输入格式

输入在一行中给出一个正整数 NN。

输出格式

若 $N$ 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 NN 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。

若 $N$ 不是性感素数，则在一行中输出 No，然后在第二行输出大于 NN 的最小性感素数。

数据范围

$1\le N\le 10^8$

输入样例1：

47

输出样例1：

Yes
41

输入样例2：

21

输出样例2：

No
23

四、代码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    

    public static void main(String[] args) {
    
        sexyPrime();
    }


    public static void sexyPrime() {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean nIsPrimeNumber = isPrimeNumber(n);
        boolean nDiffSix = isPrimeNumber(n - 6);
        if (nIsPrimeNumber && nDiffSix) {
    
            System.out.println("Yes");
            System.out.println(n - 6);
            return;
        }
        boolean nAddSix = isPrimeNumber(n + 6);
        if (nIsPrimeNumber &&  nAddSix) {
    
            System.out.println("Yes");
            System.out.println(n + 6);
            return;
        }
        System.out.println("No");
        Set<Integer> set = new HashSet<>();
        int num = n - 5;
        while (true) {
    
            if (isPrimeNumber(num)) {
    
                set.add(num);
            }
            if (set.contains(num - 6) && set.contains(num)) {
    
                System.out.println(num - 6 > n ? num - 6 : num);
                return;
            }
            num++;
        }
    }

    public static boolean isPrimeNumber(int num) {
    
        if (num <= 3) {
    
            return num > 1;
        }
        for (int i = 2; i <= Math.pow(num, 0.5); i++) {
    
            if (num % i == 0) {
    
                return false;
            }
        }
        return true;
    }

}

写在后面

欢迎关注，实现期间会经常发一些工作中遇到的问题。

欢迎随时留言讨论，与君共勉，知无不答！