关于Java大整数是否是素数
2024-10-19 21:47:47
题目描述
请编写程序，从键盘输入两个整数m，n，找出等于或大于m的前n个素数。
输入格式:
第一个整数为m，第二个整数为n；中间使用空格隔开。例如： 103 3
输出格式:
从小到大输出找到的等于或大于m的n个素数，每个一行。例如： 103 107 109
输入样例:
9223372036854775839 2
输出样例:
9223372036854775907
9223372036854775931
用到的Api：
本题代码：
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
String sc = in.next();
BigInteger m = new BigInteger(sc);
int n = in.nextInt();
int i=0;
while(i<n){
if(isPrime(m)){
System.out.println(m);
i++;
}
m=m.add(BigInteger.ONE);
}
}
public static boolean isPrime(BigInteger num) {
return num.isProbablePrime(50);
}
}
api的相关实现代码：
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite. If
* {@code certainty} is ≤ 0, {@code true} is
* returned.
*
* @param certainty a measure of the uncertainty that the caller is
* willing to tolerate: if the call returns {@code true}
* the probability that this BigInteger is prime exceeds
* (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
* this method is proportional to the value of this parameter.
* @return {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*/
public boolean isProbablePrime(int certainty) {
if (certainty <= 0)
return true;
BigInteger w = this.abs();
if (w.equals(TWO))
return true;
if (!w.testBit(0) || w.equals(ONE))
return false;
return w.primeToCertainty(certainty, null);
}
// Single Bit Operations
/**
* Returns {@code true} if and only if the designated bit is set.
* (Computes {@code ((this & (1<<n)) != 0)}.)
*
* @param n index of bit to test.
* @return {@code true} if and only if the designated bit is set.
* @throws ArithmeticException {@code n} is negative.
*/
public boolean testBit(int n) {
if (n < 0)
throw new ArithmeticException("Negative bit address");
return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
}
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*
* This method assumes bitLength > 2.
*
* @param certainty a measure of the uncertainty that the caller is
* willing to tolerate: if the call returns {@code true}
* the probability that this BigInteger is prime exceeds
* {@code (1 - 1/2<sup>certainty</sup>)}. The execution time of
* this method is proportional to the value of this parameter.
* @return {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*/
boolean primeToCertainty(int certainty, Random random) {
int rounds = 0;
int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;
// The relationship between the certainty and the number of rounds
// we perform is given in the draft standard ANSI X9.80, "PRIME
// NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
int sizeInBits = this.bitLength();
if (sizeInBits < 100) {
rounds = 50;
rounds = n < rounds ? n : rounds;
return passesMillerRabin(rounds, random);
}
if (sizeInBits < 256) {
rounds = 27;
} else if (sizeInBits < 512) {
rounds = 15;
} else if (sizeInBits < 768) {
rounds = 8;
} else if (sizeInBits < 1024) {
rounds = 4;
} else {
rounds = 2;
}
rounds = n < rounds ? n : rounds;
return passesMillerRabin(rounds, random) && passesLucasLehmer();
}
/**
* Returns true iff this BigInteger passes the specified number of
* Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
* 186-2).
*
* The following assumptions are made:
* This BigInteger is a positive, odd number greater than 2.
* iterations<=50.
*/
private boolean passesMillerRabin(int iterations, Random rnd) {
// Find a and m such that m is odd and this == 1 + 2**a * m
BigInteger thisMinusOne = this.subtract(ONE);
BigInteger m = thisMinusOne;
int a = m.getLowestSetBit();
m = m.shiftRight(a);
// Do the tests
if (rnd == null) {
rnd = ThreadLocalRandom.current();
}
for (int i=0; i < iterations; i++) {
// Generate a uniform random on (1, this)
BigInteger b;
do {
b = new BigInteger(this.bitLength(), rnd);
} while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);
int j = 0;
BigInteger z = b.modPow(m, this);
while (!((j == 0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
if (j > 0 && z.equals(ONE) || ++j == a)
return false;
z = z.modPow(TWO, this);
}
}
return true;
}
/**
* Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
*
* The following assumptions are made:
* This BigInteger is a positive, odd number.
*/
private boolean passesLucasLehmer() {
BigInteger thisPlusOne = this.add(ONE);
// Step 1
int d = 5;
while (jacobiSymbol(d, this) != -1) {
// 5, -7, 9, -11, ...
d = (d < 0) ? Math.abs(d)+2 : -(d+2);
}
// Step 2
BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);
// Step 3
return u.mod(this).equals(ZERO);
}
最新文章
- Eclipse CDT Linux下内存分析 实战历险
- Oracle日期时间
- 有关big.LITTLE，你需要知道的十件事情
- chrome浏览器关闭标签页面
- 在 MapPath 的 Path 参数中不允许出现“..”字符。
- mysql 交叉表
- [水题]ZOJ3038 Triangle War II
- ubuntu install opengrok
- 编程算法 - 连续子数组的最大和 代码(C)
- D16Pascal的编译器和IDE
- MyEclipse9,MyEclipse10 安装ADT
- python 3.6 lxml标准库lxml的安装及etree的使用注意
- 关于dfs
- 关于利用maven搭建ssm的博客，我们一起来探讨下问的最多的问题
- 八、xadmin自定义菜单栏顺序
- java Integer类以及拆箱和装箱
- CS229 6.17 Neurons Networks convolutional neural network（cnn）
- 【Android】详解Android的menu菜单
- kerberos认证的步骤，学习笔记
- GridView监听器