import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 快速判定素数,用素数判定素数。比如求1-100之间的素数,
* 先求1-10之间的素数为[2,3,5,7],
* 再用11-100的数%[2,3,5,7],不能被整除的就是素数
*/
public class Prime {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入两个数并按回车键(格式为a b):");
while (true) {
long n1 = sc.nextLong();
long n2 = sc.nextLong();
List<Long> primeList = getPrime(n1, n2);
for (Long prime : primeList) {
System.out.print(prime + " ");
}
System.out.println();
}
}
public static List<Long> getPrime(long begin, long end) {
List<Long> result = new ArrayList<Long>();// result用于保存begin-end之间的所有素数
List<Long> tempPrime = new ArrayList<Long>();// 保存2-Math.sqrt(end)之间的所有素数
for (long i = 2; i <= Math.sqrt(end); i++) {
if (isPrime(i)) {
tempPrime.add(i);
// System.out.print(i + " ");
}
}
// System.out.println();
for (long prime : tempPrime) {
if (prime >= begin) {
result.add(prime);
}
}
long start = (long) Math.sqrt(end);
if (start > begin) {
begin = start;
}
for (long i = begin; i <= end; i++) {
boolean flag = true;
for (long prime : tempPrime) {
if (i % prime == 0) {
flag = false;
break;
}
}
if (flag) {
result.add(i);
}
}
return result;
}
/**
* 直接判定一个数是否为素数
*/
public static boolean isPrime(long n) {
for (long i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
if (n <= 1L) {
return false;
}
return true;
}
}
分享到:
相关推荐
素数定义 素数判定证明 素数求解算法 素数定义 素数判定证明 素数求解算法
本资源为论文原文 当今世界上公认最新的素数判定方法 Manindra Agrawal教授和他的...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假设。
1. 素数判定问题 素数判定问题是一个非常常见的问题,本文介绍了常用的几种判定方法。 2. 原始算法 素数的定义是,除了能被1和它本身整除而不能被其他任何数整除的数。根据素数定义 只需要用2到n-1去除n,如果都除...
随机产生的任意大小的数,并验证其是否为素数。
Manindra Agrawal教授和他的两个学生Neeraj Kayal和Nitin Saxena在坎普尔印度技术研究...AKS算法证明了可以应用一个确定的算法在输入规模的多项式时间内决定一个整数是否为素数的问题,而没有使用任何未证明的数学假定
大素数的判定在公钥密码体制中起关键作用,分析了用于素数构造的相关定理及常的素数判定算法:Demytko算法、刘明华提出的素数构造算法。在莱梅定理的基础上实现素数构造算法,即由小素数组成的因数基经过多次合成和...
实现Miller-Rabin素数判定算法.zip
介绍了素数判定的几种算法。希望对大家能有用。谢谢
。。。
判断质数 素数——我知道的最快的方法.pdf
几年前3个印度人发明的判定大素数问题的最新算法--AKS素性测定算法.它的出现颠覆了无数先哲上百年的理论研究..
生成大素数,包括大整数的运算和素数的判定以及相关算法
公共密钥体系中,一般选择的素数都是相当大的(通常在100位以上),如果采用上次的试除法来判定,那么可能要穷尽你一生的时间都还不够。所以在一般的应用领域,人们采用的是Rabin-Miller检验法。 本文描述Miller-...
利用Miller_Rabin方法判断一个数是否为素数,可用于大整数的判定
10 .3 拉斯维加斯( Las Vegas)型概率算法 10 .3 .1 八皇后问题 10 .3 .2 整数因子分解问题 10 .4 蒙特卡罗(Monte Ca rlo)型概率算法 10 .4 .1 主元素问题 10 .4 .2 素数测试问题 10 .5 实验项目— — —随机数发生器...
2002年提出的AKS素判定算法是目前世界上唯一的多项式时间的素数检测算法。这里有对该算法详细的描述以及用C++的NTL大数库对算法的实现,希望能对初学信安和公钥密码的同学有所帮助。
我们给出了素数判定的无条件确定性多项式算法.doc
2. 大素数判定问题。编程实现大素数的随机生成;快速判定任意一个大数是否是素数;验证1000以内数的哥德巴赫猜想。(注:素数即只能被1和本身整除的正整数;哥德巴赫猜想:任何一个大于6的偶数都可以表示成两个素数...