当前位置: 首页 > 代码分享 > 使用Java编写求质数的程序方法

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

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

8 1
我们认为: 用户的主要目的,是为了获取有用的信息,而不是来点击广告的。因此本站将竭力做好内容,并将广告和内容进行分离,确保所有广告不会影响到用户的正常阅读体验。用户仅凭个人意愿和兴趣爱好点击广告。
我们坚信:只有给用户带来价值,用户才会给我们以回报。
CodePlayer技术交流群1CodePlayer技术交流群1

帮朋友打一个硬广告:

P2P网贷系统(Java版本) 新年低价大促销,多年P2P技术积累,系统功能完善(可按需定制,可支持第三方存管、银行存管),架构稳定灵活、性能优异、二次开发快速简单。 另可提供二次开发、安装部署、售后维护、安全培训等一条龙服务。

外行看热闹,内行看门道。可以自信地认为,在系统设计上,比市面上的晓风、迪蒙、方维、绿麻雀、国融信、金和盛等P2P系统要好。
深圳地区支持自带技术人员现场考察源代码、了解主要技术架构,货比三家,再决定是否购买。

也可推荐他人购买,一旦完全成交,推荐人可获得实际售价 10% 的返现。
有意向者,详情请 点击这里 联系,工作时间立即回复。