PAT乙级：1007 素数对猜想 (20 分)（Java）

我会带着你远行 2022-10-14 14:56 214阅读 0赞

## PAT乙级：1007 素数对猜想 (20 分)（Java） ##

> 作者 CHEN, Yue  
> 单位 浙江大学  
> 代码长度限制 16 KB  
> 时间限制 200 ms  
> 内存限制 64 MB

**题目描述：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70]  
**题解思路：  
1、首先明确素数的定义：一个大于1的自然数，且除了1和它本身外，不能被其他自然数整除的数就是素数，因此拿到一个素数n，只要n不能被\[2,n-1\]区间中的任何自然数整除，那n就是素数。  
2、找出所有素数，判定相邻两个素数是否相差2，如果是计数器+1**

**代码一：**

import java.util.Scanner;
    
    /**
     * 1007 素数对猜想 (20 分)
     *
     * @author LiFeilin
     * @date 2021年05月22日
     */
    public class Test7 {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int number = scanner.nextInt();
            int count = 0;
            int[] a = new int[1000];    //存放素数
            boolean flag = true;        //标记
            for (int i = 2; i <= number; i++) {
             //判定是否为素数
                for (int j = 2; j < i; j++) {
        
                    if (i % j == 0) {
        
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                                 //是素数，存放到数组a中
                    a[count] = i;
                    count++;
                }
                flag = true;
            }
            int n = 0;
            for (int i = 0; i < count-1; i++) {
             //遍历素数数组
                 if (a[i + 1] - a[i] == 2)          //相邻两个素数相差2
                    n++;                            //计数器+1
                else continue;
            }
            System.out.println(n);                  //输出符合条件素数对
        }
    }

**提交结果一：测试点5运行超时**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 1]

**改正：用到了sqrt()来快速查找素数，通过对目标开根号，减少计算次数。求素数时，不必从2到x-1(x/2也会超时)去循环，只需2到sqrt(x)即可，否则最后一测试点会超时、**  
**代码二：**

import java.util.ArrayList;
    import java.util.Scanner;
    
    /**
     * 1007 素数对猜想 (20 分)
     *
     * @author LiFeilin
     * @date 2021年05月22日
     */
    public class Test7 {
        
        public static boolean isPrime(int i) {
        
            if (i == 1) {
        
                return false;
            }
            if (i % 2 == 0 && i != 2) {
        
                return false;
            }
            for (int j = 3; j <= Math.sqrt(i); j += 2) {
          //用到了sqrt()来快速查找素数。通过对目标开根号，减少计算次数
                if (i % j == 0) {
        
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
        
            ArrayList list = new ArrayList();
            Scanner scanner = new Scanner(System.in);
            int number = scanner.nextInt();
            for (int i = 1; i <= number; i++) {
        
                if (isPrime(i)) {
        
                    list.add(i);
                }
            }
            int n = 0;
            for (int i = 0; i < list.size() - 1; i++) {
             //遍历素数数组
                if ((int) list.get(i + 1) - (int) list.get(i) == 2)          //相邻两个素数相差2
                    n++;                            //计数器+1
                else continue;
            }
            System.out.println(n);                  //输出符合条件素数对
        }
    }

**提交结果二：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70]: /images/20221014/3c1b3549c24b426693f146c036f8c0bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 1]: /images/20221014/a1b81469795e460a8981bcdb2eb37df1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 2]: /images/20221014/9e97e0540ac74225a98a2fb9a8aac955.png