关于加速素数计数器的建议

huangapple go评论64阅读模式
英文:

Advice on speeding up prime number counter

问题

以下是改进后的代码:

public static int countPrime(int limitNo) {
    int noOfTimes = 0;

    for (int o = 2; o <= limitNo; o++) {
        boolean isPrime = true;

        for (int i = 2; i <= Math.sqrt(o); i++) {
            if (o % i == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            noOfTimes++;
        }
    }

    return noOfTimes;
}
英文:

How can I improve the logic of the following code? The purpose is to compute the number of primes from 1 to the user input (limitNo). The program works fine except it takes a while, more than the usual 1-3 secs, to generate a result for huge numbers like 99999.

public static int countPrime(int limitNo) {
  int noOfTimes = 0, noOfRounds = 0; int o = 1;
    
  while (o &lt;= limitNo) {
    for (int i = 1; i &lt;= o; i++) {
      if (o%i == 0) {
        noOfRounds++;
      }        
    }   
    if (noOfRounds == 2) {
      noOfTimes++;
    }
    noOfRounds = 0;    
    o++;
  }
    
  return noOfTimes;
}

答案1

得分: 1

以下是翻译好的内容:

代码可以通过以下方式进行改进:

  1. 将部分代码行分离,以创建一个 isPrime() 方法。
  2. 修改 for 循环的限制条件,这样如果条件满足,意味着该数字不是质数。
public static boolean isPrime(int num) {
  for (int i = 2; i < num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}
  1. 将方法中的代码替换为 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;
}
  1. 当然,还有更好的改进方法,例如:
for (int i = 2; i <= num/2; i++)
for (int i = 2; i <= Math.sqrt(num); i++)
英文:

The code can be improved by

  1. Separating some of the lines to make an isPrime() method.

  2. Changing limits of the for loop so that if the condition is met that means the number is not prime.

    public static boolean isPrime(int num) {
      for ( int i = 2 ; i &lt; num ; i++ ) {
        if ( num % i == 0 ) {
          return false;
        }
      }
      return true;
    }
    
  3. Replacing the code in the method with isPrime() and change the start int o = 2 ;.

    public static int countPrime(int limitNo) {
      int noOfTimes = 0;
      int o = 2;
      while ( o &lt;= limitNo ) {
        if ( isPrime(o) ) {
          noOfTimes++;
        }
        o++;
      }
      return noOfTimes;
    }
    
  4. Of course, there are better and more improvements like:

    for ( int i = 2 ; i &lt;= num/2 ; i++ )
    
    for ( int i = 2 ; i &lt;= Math.sqrt(num) ; i++ )
    

huangapple
  • 本文由 发表于 2020年9月4日 11:39:38
  • 转载请务必保留本文链接:https://go.coder-hub.com/63734518.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定