首页 > 试题广场 >

学数学

[编程题]学数学

热度指数：1684 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

数学老师正在教授小畅和小游两人素数的概念。为了帮助巩固两人的知识，老师说出一个数，要求小游和小畅合作，每人说出一个素数，使得两人说出的素数的和刚好等于老师说出的数。请编写程序计算两人说出的素数对的个数。如，老师说10，小畅和小游可以说出两对素数，分别为（5,5）和（3,7）（不考虑顺序）。

输入描述:

输入包括一个整数n,(3 ≤ n < 1000)

输出描述:

输出符合条件的素数对的个数

示例1

输入

输出

算法知识视频讲解

Java

LHC0512

Java解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer> record =new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        recordPrimes(n);
        int count=0;
        
        //对于有序数组的双指针的方法
        int i=0;
        int j=record.size()-1;
        while (i<=j){
            int sum=record.get(i)+record.get(j);
            if (sum==n){
                count++; i++; j--;
            }
            else if (sum<n) i++;
            else j--;
        }
        System.out.println(count);
    }

    //比较快的判断是否为素数的方法
    static void recordPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++)
            if (isPrim[i])
                for (int j = i * i; j < n; j += i)
                    isPrim[j] = false;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) record.add(i);
    }
}

发表于 2020-03-01 10:22:41 回复(0)