java求素数的两种方法
程序员文章站
2022-06-21 13:43:04
求200-500之间所有素数思想一 试除法要判断X是否为质数,就从2一直尝试到x-1做法效率差,可适当修改循环控制条件稍微加强效率 int count2 = 0;// for (int j = 200; j < 500; j++) { for (int j = 201; j < 500; j +=2) { boolean flag = true;// for (int j2 = 2; j2 < j; j2++) {// if (j%j2 == 0) {...
求200-500之间所有素数
思想一 试除法
要判断X是否为质数,就从2一直尝试到x-1
做法效率差,可适当修改循环控制条件稍微加强效率
int count2 = 0;
// for (int j = 200; j < 500; j++) {
for (int j = 201; j < 500; j +=2) {
boolean flag = true;
// for (int j2 = 2; j2 < j; j2++) {
// if (j%j2 == 0) {
// flag = false;
// break;
// }
// }
for (int j2 = 2; j2 < j/2; j2++) {
if (j%j2 == 0) {
flag = false;
break;
}
}
if (flag) {
System.out.print(j+" ");
count2++;
if (count2 % 8 == 0) {
System.out.println();
}
}
}
// 211 223 227 229 233 239 241 251
// 257 263 269 271 277 281 283 293
// 307 311 313 317 331 337 347 349
// 353 359 367 373 379 383 389 397
// 401 409 419 421 431 433 439 443
// 449 457 461 463 467 479 487 491
// 499
思想二 筛选法
该方法思想的百度百科
2是公认最小的质数,先把所有2的倍数去掉;
然后剩下的那些大于2的数里面,最小的是3,3也是质数;
然后把所有3的倍数都去掉,剩下的那些大于3的数里面,最小的是质数5,上述过程不断重复,就可以把某个范围内的合数全都除去(就像被筛子筛掉一样),剩下的就是质数了。
实现步骤
- 构造一个定长的标记数组,通常是boolean型,长度是所求范围的最大值+1,于是下标代表该范围的所有数字。(该题若求质数个数 用int数组更简单)
- 布尔类型默认全是false,也可以不初始化。只需要修改条件。
- 是当前最小数倍数就被标记。
- 循环筛选结束后,判断标记数组的值若没被标记,则打印下标。
int[] flag2 = new int[500];//下标与元素相等
for (int j = 2; j < Math.sqrt(flag2.length); j++) {
if (flag2[j] == 1) {// 最小的除数是合数 就下一次
continue;
}
for (int j2 = 3; j2 < flag2.length; j2++) {
if (flag2[j2] == 1) {//已经标记的就跳过
continue;
}
if (j2 % j == 0) {//将是j的倍数的数剔除 标记为1
flag2[j2] = 1;
}
}
}
int count6 = 0;
for (int j = 201; j < flag2.length; j +=2) {
if (flag2[j] == 0) {
System.out.print(j+" ");
count6++;
if (count6 % 8 == 0) {
System.out.println();
}
}
}
System.out.println();
// 211 223 227 229 233 239 241 251
// 257 263 269 271 277 281 283 293
// 307 311 313 317 331 337 347 349
// 353 359 367 373 379 383 389 397
// 401 409 419 421 431 433 439 443
// 449 457 461 463 467 479 487 491
// 499
本文地址:https://blog.csdn.net/cora_99/article/details/107374326
上一篇: mybatis_3源码阅读日记_容器的加载与初始化
下一篇: Java基础(持续更新)