首页 > 代码库 > 腾讯2017秋招笔试_素数对 java程序
腾讯2017秋招笔试_素数对 java程序
[编程题] 素数对
时间限制：1秒
空间限制：32768K
给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）
输入描述:
输入包括一个整数n,(3 ≤ n < 1000)
输出描述:
输出对数
输入例子1:
10
输出例子1:
2
Java源码
import java.util.Scanner;
import java.util.TreeSet;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt();
if(n>=1000||n<3){
continue;
}
System.out.println(getPrimeNums(n));
}
sc.close();
}
/** 获得一个正整数的素数对的个数*/
public static int getPrimeNums(int n){
TreeSet<Integer> set=getPrimeSet(n);
int num=0;
for (Integer one : set)
{
int other=n-one;
/**判断二个数(one,other)是否为素数对*/
if(set.contains(other)&&(one<=other)){
num++;
}
}
return num;
}
/** 获得一个数的所有素数，用TreeSet<Integer>表示*/
public static TreeSet<Integer> getPrimeSet(int n){
TreeSet<Integer> set=new TreeSet<Integer>();
for(int i=2;i<=n;i++){
if(isPrime(i))
{
set.add(i);
}
}
return set;
}
/** 判断一个数是否为素数*/
public static boolean isPrime(int n){
for(int i=2;i<=(int)Math.sqrt(n);i++){
if(n%i==0) return false;
}
return true;
}
}
腾讯2017秋招笔试_素数对 java程序