哥德巴赫猜想实验报告"/>
java哥德巴赫猜想实验报告
验证哥德巴赫猜想：任何一个大于 6 的偶数，都能分解成两个质数的和。要求输入一个整数，输出这个
数能被分解成哪两个质数的和。
eg : 14
14=3+11
14=7+7
public class TestGoldbach{
public static void main(String[] args){
java.util.Scanner s = new java.util.Scanner(System.in);
int n = s.nextInt();
//输入大于 6 的偶数
while (n<6 || n%2!=0) {
System.out.println("Error!");
n = s.nextInt();
}
for(int a = 3 ; a <= n/2 ; a+=2){
int b = n-a;
if (isPrime(a) && isPrime(b)){
System.out.println(n+"="+a+"+"+b);
}
}
}
//判断m是不是质数
static boolean isPrime(int m){
double d = Math.sqrt(m);
for(int i =3 ; i <= d ; i+=2){
if (m % i == 0) return false;
}
return true;
}
}
下面是对isPrime方法进行优化：
//判断一个数是质数
优化前：
static boolean isPrime(int n){
for (int j = 2; j <= n; j++) {
if (n % j == 0) return false;
}
return true;
}
优化1：
在哥德巴赫猜想中，一个数的因子是成对出现的，如：
100 = 2 * 50
= 4 * 25
= 5 * 20
= 10 * 10
所以，一个数n,它的的因子，一个肯定是<=根号下n，一个肯定是>=根号下n
所以，不用找>=根号下n的因子，只有有<=根号下n的因子，就点有>=根号下n的因子
所以，搜索范围就到根号下n即可
static boolean isPrime(int n){
for (int j = 2; j <= Math.sqrt(n); j++) {
if (n % j == 0) return false;
}
return true;
}
再优化：
//判断m是不是质数
static boolean isPrime(int m){
double d = Math.sqrt(m);
//从i=3开始，每次i+=2,即是只找奇数就行，因为大于0的偶数都不是质数
//此题中，是判断一个数可以拆分成某两个数，看拆分后的数是不是质数
for(int i =3 ; i <= d ; i+=2){
if (m % i == 0) return false;
}
return true;
}
更多推荐
java哥德巴赫猜想实验报告
发布评论