java实现找素数
JAVA 实现 素数
2023-09-14 08:58:09 时间
** 找素数**
素数就是不能再进行等分的整数。比如:7,11。而9不是素数,因为它可以平分为3等份。一般认为最小的素数是2,接着是3,5,…
请问,第100002(十万零二)个素数是多少?
请注意:“2” 是第一素数,“3” 是第二个素数,依此类推。
不需要提交源代码,只要写出准确的结果即可!
答案写在:“解答.txt”中,不要写在这里。
参考答案:
1299743
import java.math.BigInteger;
public class Main1 {
//方法1:使用大整数,自带判断素数方法,算出最终结果大约要1分钟
public void printResult1() {
int count = 1;
BigInteger a = new BigInteger("3");
BigInteger b = BigInteger.ONE;
for(int i = 3;i < 10000000;i++){
if(a.isProbablePrime(i)) {
count++;
}
if(count == 100002) {
System.out.println(a);
break;
}
a = a.add(b);
}
return;
}
//方法2:使用埃拉托色尼筛选法,算出结果大约10秒
public void printResult2() {
int[] A = new int[10000000];
for(int i = 2;i < 10000000;i++)
A[i] = i;
for(int i = 2;i < 4000;i++) { // 4000 * 4000 > 10000000,此处是因为i*i为i的当前条件下最小合数
int j = 0;
if(A[i] != 0)
j = i * i; //i的合数起始最小位置
while(j < 10000000) {
A[j] = 0;
j = j + i; //依次递增i个位置的数均是i的合数
}
}
int count = 0;
for(int i = 2;i < 10000000;i++) {
if(A[i] != 0)
count++;
if(count == 100002) {
System.out.println(A[i]);
break;
}
}
return;
}
public static void main(String[] args) {
Main1 test = new Main1();
test.printResult2();
}
}
相关文章
- 几种任务调度的 Java 实现方法与比较
- Java实现 LeetCode 798 得分最高的最小轮调 (暴力分析)
- Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)
- Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)
- Java实现 LeetCode 337 打家劫舍 III(三)
- Java实现 洛谷 P1217 [USACO1.5]回文质数 Prime Palindromes
- java实现第N个素数
- java实现第N个素数
- java实现第N个素数
- java实现孪生素数
- java实现孪生素数
- java实现找素数
- java实现第四届蓝桥杯梅森素数
- java实现第四届蓝桥杯有理数类
- java实现第四届蓝桥杯组素数
- java实现第四届蓝桥杯组素数
- java实现第四届蓝桥杯组素数
- Java实现第九届蓝桥杯阶乘位数
- Java实现第九届蓝桥杯阶乘位数
- Java实现判断单联通(强连通缩点+拓扑排序)Going from u to v or from v to u
- Java实现 蓝桥杯VIP 算法提高 密码锁
- Atitit 搜索蓝牙设备 powershell的实现 java noede.js python 先用脚本语言python nodejs,不好实现。。Java 也不好实现。。 Netcore可以,
- JAVA语言之Java 中不同的并行实现的性能比较