当前位置:首页>java>耿老师教你学Java:大素数

耿老师教你学Java:大素数

  • 2026-09-10 21:21:28
耿老师教你学Java:大素数

大素数

内容摘自《Java JDK实用编程方法和算法》
第2章-2.1
推荐阅读:
新书《Java JDK 实用编程方法与算法》出版发行

   在许多和计算有关的Java程序中,java.math 包中的类发挥着关键作用,此包的类专门用于处理大整数运算以及高精度浮点数运算。大部分“Java 程序设计课程” 都会涵盖该包的基础内容。针对java.math 包,本章对其进一步深挖拓展,精心挑选实例,助力读者更全面、更深入地掌握java.math包中类的应用精髓,提升在实际编程中使用java.math 包中类的能力。相对其它包,java.math包中的类很少,只有四个类:BigDecimal,BigInteger,MathContext和RoundingMode类,因此,本章以实际问题作为章节的标题讲解java.math 包的类的用法和实例。

2.1 大素数

    BigInteger 类位于java.math包中,用于处理非常大的整数。Java中的基本数据类型 int和long能表示的整数范围是有限的,当需要处理非常大的整数时,比如处理非常大的素数,就可以使用BigInteger类。可以用两种方法创建BigInteger对象,一种是用BigInteger的构造函数(常用):BigInteger(String val),例如:

BigInteger num = new BigInteger("12345678901234567890");

另一种是使用BigInteger的静态方法:BigInteger valueOf(long val),例如:

BigInteger num = BigInteger.valueOf(12367839L);

BigInteger类同时也提供了一些如下的实用的算法。

1.public BigInteger add(BigInteger val):返回当前大整数和参数指定的大整数的val的和 。

2.public BigInteger subtract(BigInteger val):返回当前大整数和参数指定的大整数的val的差。

3.public BigInteger multiply(BigInteger val):返回当前大整数和参数指定的大整数的val的积。

4.public BigInteger divide(BigInteger val):返回当前大整数和参数指定的大整数的val的商(舍去余数)。

5.public BigInteger remainder(BigInteger val):返回当前大整数和参数指定的大整数的val的余数。

6.public BigInteger gcd(BigInteger val):返回当前大整数和参数指定的大整数的val的最大公约数。

7.public BigInteger pow(int exponent):返回当前大整数exponent次幂。

8.BigInteger nextProbablePrime():从当前大整数开始往后寻找第一个可能是素数的数,并返回这个素数。需要注意的是,这里说的 “可能” 是因为该方法使用的是概率性素性测试(Miller - Rabin测试),在实际应用中,误判的概率极低。

例子2.1输出一些小素数,计算了大素数的乘积,以及两个大数的最大公约数。
import java.math.BigInteger;public class Ex2_1 {    public static void main(String[] args) {        // 初始化起始值和上限值        BigInteger start = BigInteger.ONE;        BigInteger limit = new BigInteger("100");        System.out.print("小素数(最大的是100之后的第一个素数):");        // 遍历寻找小素数        BigInteger currentPrime = start;        while (currentPrime.compareTo(limit) < 0) {            currentPrime = currentPrime.nextProbablePrime();            System.out.print(" " + currentPrime);        }        System.out.println();        // 定义两个大整数        BigInteger largeNumber1 = new BigInteger("969876592");        BigInteger largeNumber2 = BigInteger.valueOf(56897628);        // 计算最大公约数        BigInteger gcd = largeNumber1.gcd(largeNumber2);        System.out.println(largeNumber1+"和"+largeNumber2+"的最大公约数是:"+gcd);        // 查找下一个可能的素数        BigInteger nextPrime1 = largeNumber1.nextProbablePrime();        BigInteger nextPrime2 = largeNumber2.nextProbablePrime();        System.out.println(largeNumber1 + " 的下一个可能的素数是: " + nextPrime1);        System.out.println(largeNumber2 + " 的下一个可能的素数是: " + nextPrime2);        // 计算两个素数的乘积        BigInteger product = nextPrime1.multiply(nextPrime2);        System.out.println(nextPrime1 + " 乘以 " + nextPrime2 + " = " + product);        // 判断素数        System.out.println(nextPrime1 + " 是素数吗? " + isPrime(nextPrime1));        System.out.println(nextPrime2 + " 是素数吗? " + isPrime(nextPrime2));    }    //判断一个 BigInteger 是否为素数    static boolean isPrime(BigInteger number) {        if (number.compareTo(BigInteger.ONE) <= 0) {            return false;        }        BigInteger limit = number.sqrt();        for(BigInteger i = BigInteger.TWO; i.compareTo(limit) <= 0;                                            i = i.add(BigInteger.ONE)) {            if (number.remainder(i).equals(BigInteger.ZERO)) {                return false;            }        }        return true;    }}    
推荐阅读:
墨香知己,温馨岁月-致清华社编辑

最新文章

随机文章