试题描述
试题代码
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;
}
}
网友评论