欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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,上述过程不断重复,就可以把某个范围内的合数全都除去(就像被筛子筛掉一样),剩下的就是质数了。

实现步骤

  1. 构造一个定长的标记数组,通常是boolean型,长度是所求范围的最大值+1,于是下标代表该范围的所有数字。(该题若求质数个数 用int数组更简单)
  2. 布尔类型默认全是false,也可以不初始化。只需要修改条件。
  3. 是当前最小数倍数就被标记。
  4. 循环筛选结束后,判断标记数组的值若没被标记,则打印下标。
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

相关标签: java案例 java