Day013 PAT乙级 1007 素数对猜想

PAT乙级 1007 素数对猜想

题目

分析

这题首先得计算出一个范围内的所有素数，然后将相邻的两个素数相减，如果等于2，则算作一个素数对，求一共有多少个素数对
题目的关键在于时间限制在200ms以内，如何减少程序的计算量是最重要的
首先得求出素数，使用两个for循环嵌套，外循环的变量i是被除数，内循环的变量j是除数。i%j求余，如果等于0说明i不是素数，如果不等于0；则是素数，记录下来
记录两次计算的结果，相减，如果等于2，就用一个变量记录下来，加1，最后输出这个变量

代码

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
    int x, y = 0;
    int count = 0;
    for (int i = 3; i <= n; ++i) {
        int flag = 1;
        for (int j = 2; j < sqrt(i); ++j) {
            if (int(i) % j== 0) {
                flag = 0;
                break;
            }
        }
        if (flag == 1) {
            x = y;
            y = (int) i;
            if (y - x == 2) ++count;
        }
    }
    cout<<count;
	return 0;
}

Java

相同的代码C++可以通过，Java却超时了

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int x, y = 0;
        int count = 0;
        for (int i = 3; i <= n; ++i) {
            int flag = 1;
            for (int j = 2; j < Math.sqrt(i); ++j) {
                if (i % j == 0) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                x = y;
                y = (int) i;
                if (y - x == 2) ++count;
            }
        }
        System.out.println(count);
        cin.close();
    }
}

优化

由于偶数都能被2整除，所以在外循环中，将 ++i 变成 i=i+2 ，只用计算奇数
一个数的因数都是成对存在的，比如24，它的因数有1,2,3,4,6,8,12,24，一共有4对，也就是说如果在√24前中没有因数，那么√24后面也没有因数，因此j的范围可以从n变成√24，
如果一个数不能被比他小的素数整除，那么这个数就是素数，所以我们可以将每次计算得到的素数保存下来，之后只要对比能否被这些素数整除就行了，可以用一个数组存储这些素数，用一个变量来记录素数的个数，所以可以将 if(i%j==0) 变成 if(i%num[j]==0) ，对j的判断条件再加上一个 j<count
最后我们就可以得到以下代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] num = new int[10000];//存储素数
        num[0] = 2;//第一个素数为2
        int count = 1;//素数的个数
        int sum = 0;//素数对的个数
        for (int i = 3; i <= n; i += 2) {
            boolean flag = true;
            for (int j = 0; j < count && j < Math.sqrt(i); ++j) {
                if (i % num[j] == 0) {//判断是否为素数
                    flag = false;
                    break;
                }
            }
            if (flag) {
                num[count] = i;//如果是素数就把它保存进数组
                if (i - num[count - 1] == 2) ++sum;//判断当前素数与上个素数相减是否等于2
                ++count;
            }
        }
        System.out.println(sum);
        cin.close();
    }
}