美文网首页
PAT-B-1007. 素数对猜想 (Java)

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

作者: GeekMonKey | 来源:发表于2016-12-01 11:29 被阅读93次

    试题描述

    试题代码

    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:PAT-B-1007. 素数对猜想 (Java)

          本文链接:https://www.haomeiwen.com/subject/qtexmttx.html