加速素数计数器的建议

tvokkenx 于 2021-07-05 发布在 Java

关注(0)|答案(1)|浏览(243)

如何改进以下代码的逻辑？目的是计算从1到用户输入（limitno）的素数。这个程序运行得很好，只是它需要一段时间，比通常的1-3秒要长，才能为99999这样的大数字生成一个结果。

public static int countPrime(int limitNo) {
  int noOfTimes = 0, noOfRounds = 0; int o = 1;

  while (o <= limitNo) {
    for (int i = 1; i <= o; i++) {
      if (o%i == 0) {
        noOfRounds++;
      }        
    }   
    if (noOfRounds == 2) {
      noOfTimes++;
    }
    noOfRounds = 0;    
    o++;
  }

  return noOfTimes;
}

Java loops

来源：https://stackoverflow.com/questions/63734518/advice-on-speeding-up-prime-number-counter

1条答案

按热度按时间

vcudknz31#

代码可以通过
把一些线分开做成一条线 isPrime() 方法。
变化的极限 for 循环，如果满足条件，则表示该数字不是素数。

public static boolean isPrime(int num) {
  for ( int i = 2 ; i < num ; i++ ) {
    if ( num % i == 0 ) {
      return false;
    }
  }
  return true;
}

将方法中的代码替换为 isPrime() 改变开始 int o = 2 ; .

public static int countPrime(int limitNo) {
  int noOfTimes = 0;
  int o = 2;
  while ( o <= limitNo ) {
    if ( isPrime(o) ) {
      noOfTimes++;
    }
    o++;
  }
  return noOfTimes;
}

当然，还有更多更好的改进，如：

for ( int i = 2 ; i <= num/2 ; i++ )

for ( int i = 2 ; i <= Math.sqrt(num) ; i++ )

赞(0）回复(0）举报 2021-07-05

我来回答

加速素数计数器的建议

1条答案

相关问题

热门标签

最新问答