【JAVA】1007 素数对猜想 (20分) PAT乙级 PAT (Basic Level) Practice (中文)

我会带着你远行 2022-12-24 09:57 179阅读 0赞

### 你是最棒的 ###

*  前言
 *  题目：1007 素数对猜想 (20分)
 *  要点：
 *  代码

# 前言 #

> **学得越多，不会得越多  
> 种一颗树的最佳时间是十年前，其次就是现在**  
>

> pat所有题解代码都会陆续上传到Github，请好兄弟们自行下载：[https://github.com/233zzh/PAT][https_github.com_233zzh_PAT]  
> qq交流群：1107710098

# 题目：1007 素数对猜想 (20分) #

> [题目链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744][https_pintia.cn_problem-sets_994805260223102976_problems_994805317546655744]

让我们定义  d  n d\_n dn 为： d  n   d\_n dn =  p n + 1 p\_\{n+1\} pn\+1 − p n p\_n pn，其中  p  i p\_i pi 是第i个素数。显然有  d 1 d\_1 d1 =1，且对于 n>1 有  d  n d\_n dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数 N(<  1 0 5 10^5 105 )，请计算不超过N的满足猜想的素数对的个数。

**输入格式:**  
输入在一行给出正整数N。

**输出格式:**  
在一行中输出不超过N的满足猜想的素数对的个数。

**输入样例:**  
20

**输出样例:**  
4

# 要点： #

第二次for循环要用 `2 ~ 平方`去判断`i` 能不能被整除，而不是`2 ~ i`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70]

# 代码 #

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: 张志浩 Zhang Zhihao * @Email: 3382885270@qq.com * @Date: 2020/11/26 * @Time: 22:08 * @Version: 1.0 * @Description: Description */
    public class Prime2 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            sc.close();
            int first_prime = 2;
            int count = 0;
            for (int i = 3; i <= N; i++) { 
                int j;
                int temp = (int) Math.sqrt(i);
                for (j = 2; j <= temp; j++) { 
                    if (i % j == 0) { 
                        break;
                    }
                }
                if (j == (temp + 1)) { 
    // System.out.println(i);
                    if ((i - first_prime) == 2) { 
                        count++;
                    }
                    first_prime = i;
                }
            }
            System.out.println(count);
        }
    }

[https_github.com_233zzh_PAT]: https://github.com/233zzh/PAT
[https_pintia.cn_problem-sets_994805260223102976_problems_994805317546655744]: https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70]: /images/20221120/94f34c34885044028f07804ac2d25871.png