如何有效确定素数?

了解有关确定给定数是否为质数的有效算法。还学习在Java 8程序中实现素数算法

1.质数

质数是大于1的自然数,不能通过将两个非1的较小自然数相乘而形成。

换句话说,质数(P)是大于1的数,其唯一因子是1,而数(P)本身。

例如,3是质数,因为它只能除以1和3(本身)。但是,4不是质数,因为它可以除以2,即可以写为2 x 2

有无限多个质数。换句话说'2, 3, 5, 7, 11, 13, ...',质数的序列永远不会结束。

2.计算素数的算法

请注意,没有已知的有效公式(经过数学验证)可以确定数字是否为质数。

通常,我们可以通过以下步骤确定数字是否为质数:

  1. 2仅是质数,也是偶数。因此,如果给定数字N为2,则它是PRIME数字。
  2. 如果给定的数字N是偶数,则它不是NOTPRIME数字。
  3. 找出N的平方根。遍历所有奇数直到,sqrt(N)并尝试用当前奇数指定N。如果任何奇数的余数为0,则数字为非素数。
  4. 其他-数字为PRIME。
boolean isPrime(int number) 
{
	if(number <= 2)
		return number == 2;
	else
		return  (number % 2) != 0 
				&&
				IntStream.rangeClosed(3, (int) Math.sqrt(number))
				.filter(n -> n % 2 != 0)
		        .noneMatch(n -> (number % n == 0));
}

3. Java程序确定素数

让我们在Java 8中实现上述素数算法。我们使用了IntStream,它有助于生成支持顺序和并行聚合操作的整数序列。

package com.how2codex.example;

import java.util.stream.IntStream;

public class Main 
{
	public static void main(String[] args) 
	{
		System.out.println("2 is prime number :: " + isPrime(2));
		System.out.println("3 is prime number :: " + isPrime(3));
		System.out.println("4 is prime number :: " + isPrime(4));
		System.out.println("5 is prime number :: " + isPrime(5));
		System.out.println("6 is prime number :: " + isPrime(6));
		System.out.println("7 is prime number :: " + isPrime(7));
		System.out.println("8 is prime number :: " + isPrime(8));
		System.out.println("9 is prime number :: " + isPrime(9));
		System.out.println("10 is prime number :: " + isPrime(10));
		System.out.println("11 is prime number :: " + isPrime(11));
	}
	
	static boolean isPrime(int number) {
		if(number <= 2)
			return number == 2;
		else
			return  (number % 2) != 0 
					&&
					IntStream.rangeClosed(3, (int) Math.sqrt(number))
					.filter(n -> n % 2 != 0)
			        .noneMatch(n -> (number % n == 0));
	}
}

程序输出。

2 is prime number :: true
3 is prime number :: true
4 is prime number :: false
5 is prime number :: true
6 is prime number :: false
7 is prime number :: true
8 is prime number :: false
9 is prime number :: false
10 is prime number :: false
11 is prime number :: true

请问您有关如何确定给定数字在Java中是质数的问题

学习愉快!

参考文献:

维基百科
IntStream Java文档

saigon has written 1440 articles

Leave a Reply