PAT-B-1007. 素数对猜想 (Java)

试题描述

试题代码

package com.hym.PAT_B;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by ymhou on 2016/11/14.
 * 两种方案
 * 最后一个测试点内存超限，得18分
 */
public class PAT_B_1007 {
    public static void main(String[] args) {
        plan1();
    }

    public static void plan1(){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int num=1;
        int count=0;
        while(GetnPrime(num) < N){
            if(GetnPrime(num+1) > N){
                break;
            }
            if(GetnPrime(num+1)-GetnPrime(num)==2){
                count++;
            }
            num++;
        }
        System.out.println(count);
    }

    public static void plan2() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int i=0;
        int count=0;
        while(i<GetNPrimeList(N).size()){
            if(i+1 >= GetNPrimeList(N).size()){
                break;
            }
            if(GetNPrimeList(N).get(i+1)-GetNPrimeList(N).get(i) == 2){
                count++;
            }
            i++;
        }
        System.out.println(count);
    }

    public static int GetnPrime(int count){
        List<Integer> list = new ArrayList<Integer>();
        int startNumber = 1;
        while(list.size() < count){
            if(IsPrime(startNumber,list)){
                list.add(startNumber);
            }
            startNumber++;
        }
        return --startNumber;
    }

    public static boolean IsPrime(int number,List<Integer> list){
        if(number == 1){
            return false;
        }
        int max = (int)Math.sqrt(number);
        for (int n:list) {
            if(number % n ==0){
                return false;
            }
            if(n > max){
                break;
            }
        }
        return true;
    }

    public static List<Integer> GetNPrimeList(int N){
        List<Integer> list = new ArrayList<>();
        int startNumber = 1;
        list.add(2);
        while(list.get(list.size()-1) <= N){
            startNumber++;
            if(startNumber > N){
                break;
            }
            if (IsPrime(startNumber,list)){
                list.add(startNumber);
            }

        }
        return list;
    }
}