AcWing——4268. Sexy element

4268. Sexy element

One 、 Test link

Point me to jump

Two 、 Topic analysis

difficulty ： Simple
when / Empty limit ：0.4s / 64MB
source ：PAT Class a real topic 1156
Algorithm tags ： enumeration Prime number Trial division

3、 ... and 、 Title Description

“ Sexy prime ” It is shaped like $(p,p+6)$ Such a pair of prime numbers .

It's called , Because the Latin tube “ 6、 ... and ” It's called “sex”（ That is, English “ sexy ”）.

Now give an integer , Please judge whether it is a sexy prime .

Input format

Input gives a positive integer on a line NN.

Output format

if $N$ It's a sexy prime , Output in one line Yes, And output and on the second line NN Another sexy prime paired （ If such a number is not unique , The one with the smaller output ）.

if $N$ Not a sexy prime , Output in one line No, Then output greater than... On the second line NN The minimum number of sexy prime .

Data range

$1\le N\le 10^8$

sample input 1：

47

sample output 1：

Yes
41

sample input 2：

21

sample output 2：

No
23

Four 、 Code

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;
    }

}

Written in the back

Welcome to your attention , During the implementation, some problems encountered in the work will often be sent .

Please feel free to leave a message to discuss , Let me share with you , Know all but answer ！