PAT-BASIC1007——素数对猜想

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

原题链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

题目描述：

知识点：素数

思路：列出不超过N的所有素数，再计算相邻且差为2的素数对数量

判别一个数是否是素数时，用开根号，而不是取半，这样能降低时间复杂度，防止超时。

1既不是素数和不是合数。

2是素数。

时间复杂度是O(n ^ 1.5)，空间复杂度是O(n)，其中n为输入的数字。

C++代码：

#include<iostream>
#include<vector>
#include<math.h>

using namespace std;

bool isPrime(int num);

int main() {
	int n;
	cin >> n;

	vector<int> primes;
	int count = 0;

	for (int i = 2; i <= n; i++) {
		if (isPrime(i)) {
			if (primes.size() != 0 && primes[primes.size() - 1] == i - 2) {
				count++;
			}
			primes.push_back(i);
		}
	}
	cout << count;
}

bool isPrime(int num) {
	for (int i = 2; i <= sqrt(num); i++) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}

C++解题报告：

JAVA代码：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int index = 0;
        int result = 0;
        int[] primes = new int[num];
        for (int i = 2; i <= num; i++) {
            if (isPrime(i)) {
                primes[index++] = i;
                if (index < 2) {
                    continue;
                }
                if (primes[index - 1] - primes[index - 2] == 2) {
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    private static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

JAVA解题报告：