PTA-乙级1007 素数对猜想 (20 分)-JAVA

PTA-乙级1007 素数对猜想 (20 分)-JAVA

题意: 前面的式子我看的不是很明白,但是从“素数对猜想”,认为这里就可以看明白这道题让我们做什么了,存在无穷多对相邻且整数差为2的素数,这是解题的关键,大致来说就是让我们输入一个这个数N,让我们判断N中所有相邻素数中相差2的素数对个数,从输入案例也可以验证一下(3和5、5和7、7和9、11和13)。   思路: 首先我们要先把给我们的N中的素数求出来,接下来在求素数对,求素数的算法我们可以用两层for循环来解决,但是在pta中提交时最后一个案例超时了,鉴于我的水平,暂时还没有学会新的求素数算法,只能拿18分了,对于求素数对,我们可以用rear和fron分别t暂存判断出来的后面的素数和前面的素数,然后对是否构成素数对判断,判断后还要记得更新front,让我们来看一下代码吧。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入正整数,注意正整数的范围
        int num = sc.nextInt();
        int count = 0;
        int rear = 0, front = 0;
        //循环从2到num之间的数,判断素数
        for (int x = 3; x <= num; x++) {	//从3开始是2和3不是素数对,不用判断2了
            boolean flag = true;	//注意开关flag的位置
            for (int i = 2; i < x; i++) {
                if (x % i == 0) {
                    flag = false;
                    break;	//x对j只要求余数为0就一定不是素数,改变控制判断素数对的开关后就跳出内循环
                }
            }
            if (flag) {
                rear = x;	//先把判断出来的第一个素数给rear,等第二次后才能真正的去判断
                if (rear - front == 2) {
                    count++;	//判断成功计数器加一
                }
                front = rear;	//更新front
            }
        }
        System.out.println(count);
    }
}

 

上一篇:Simple Problem with Integers (线段树更新懒惰值+区间和)


下一篇:poj 1007(sort函数的重写)