您的浏览器过于古老 & 陈旧。为了更好的访问体验, 请 升级你的浏览器
Ready 发布于2014年02月13日 05:05 最近更新于 2019年05月22日 11:33

原创 使用Java编写求质数的程序方法

174 次浏览 读完需要≈ 9 分钟 Java

内容目录

请直接参考以下Java代码:

代码版本一

本方法的实现思路是:由于大于3的偶数都能够被2整除,所以不可能是质数;因此依次取大于3的奇数,分别与小于的所有质数相除,如果该奇数不能被任何一个质数整除,则证明其为质数。

package test;

public class Test {
    // 程序主方法
    public static void main(String[] args) {

        long[] primes = getPrimes(20);

        // 输出数组中的所有质数,每行5个
        for (int i = 0; i < primes.length; i++) {
            if (i % 5 == 0) {                    
                System.out.println();
            }
                    System.out.print(primes[i]);
            System.out.print('\t');
        }
    }

    /**
     * 获取"2~正无穷"的连续质数排列的前primeCount个,并以long[]的数组形式返回
     * @param primeCount 指定质数数组中元素的个数
     */
    public static long[] getPrimes(int primeCount) {

        // 如果个数不是正数,直接返回
        if (primeCount <= 0) {
            return new long[0];
        }

        // 用于存储质数的数组
        long[] primeArray = new long[primeCount];
        // 已经获得的质数个数
        int count = 0;

        // 特殊处理第1个质数,作为已知质数直接放进数组
        if (primeCount > 0) {
            primeArray[0] = 2;
            count++;
        }
		
        // 特殊处理第2个质数,作为已知质数直接放进数组
        if (primeCount > 1) {
            primeArray[1] = 3;
            count++;
        }
		
        // 用于进行循环验证的初始数值
        int number = 3;
        // 判断当前整数是否为质数的标识变量
        boolean isNotPrime = false;

        while (count < primeCount) {
            // 大于3的偶数不可能是质数,每次直接+2,只取奇数进行判断即可
            number += 2;
            isNotPrime = false;

            for (int i = 0; i < count; i++) {
                isNotPrime = number % primeArray[i] == 0;
                // 如果当前整数能够被小于它的质数整除,则表明它不是质数,直接跳出当前循环
                if (isNotPrime) {
                    break;
                }
            }

            // 如果当前整数是质数,放进质数数组中
            if (!isNotPrime) {
                primeArray[count] = number;
                count++;
            }
        }
        return primeArray;
    }
}

程序输出如下:

2	3	5	7	11	
13	17	19	23	29	
31	37	41	43	47	
53	59	61	67	71

代码版本二

本方法的实现思路是:由于大于3的偶数都能够被2整除,所以不可能是质数;因此依次取大于3的奇数,分别与小于或等于它的平方根的所有质数相除,如果该奇数不能被任何一个质数整除,则证明其为质数。

/**
 * 获取"2~正无穷"的连续质数排列的前primeCount个,并以long[]的数组形式返回
 * @param primeCount 指定质数数组中元素的个数
 */
public static long[] getPrimes(int primeCount) {
	
	// 如果个数不是正数,直接返回
	if (primeCount <= 0) {
		return new long[0];
	}
	
	// 用于存储质数的数组
	long[] primeArray = new long[primeCount];
	// 已经获得的质数个数
	int count = 0;
	
	// 特殊处理第1个质数,作为已知质数直接放进数组
	if (primeCount > 0) {
		primeArray[0] = 2;
		count++;
	}
	
	// 特殊处理第2个质数,作为已知质数直接放进数组
	if (primeCount > 1) {
		primeArray[1] = 3;
		count++;
	}
	
	// 用于进行循环验证的初始数值
	int number = 3;
	// 判断当前整数是否为质数的标识变量
	boolean isNotPrime = false;
	
	while (count < primeCount) {
		// 大于3的偶数不可能是质数,每次直接+2,只取奇数进行判断即可
		number += 2;
		isNotPrime = false;
		
		double sqrt = Math.sqrt(number); 
		for (int i = 0; i < count; i++) {
			if (sqrt < primeArray[i]) {
				//如果当前质数大于该整数的平方根,则直接跳出循环
				break;					
			}
			isNotPrime = number % primeArray[i] == 0;
			// 如果当前整数能够被小于它的质数整除,则表明它不是质数,直接跳出当前循环
			if (isNotPrime) {
				break;
			}
		}
		
		// 如果当前整数是质数,放进质数数组中
		if (!isNotPrime) {
			primeArray[count] = number;
			count++;
		}
	}
	return primeArray;
}

上述两种方法的区别是:前者是与小于该奇数的质数进行相除判断,后者是与小于或等于该奇数的平方根的质数进行相除判断。在方法二中,每个奇数与质数进行求余判断的次数要远远小于方法一,但是会增加对每个奇数求平方根的一次额外开销,请根据个人需要酌情选择。

  • CodePlayer技术交流群1
  • CodePlayer技术交流群2

0 条评论

撰写评论