查找下一个质数的最佳方法（Java） [英] Optimal way to find next prime number (Java)

问题描述

我被要求编写一个程序以最佳方式查找下一个质数。我写了这段代码，但是找不到最佳答案。有任何建议吗？

I was asked to write a program to find next prime number in an optimal way. I wrote this code, but I could not find an optimal answer to it. Any suggestions?

public  static int nextPrime(int input) {

    input++;
    //now find if the number is prime or not

    for(int i=2;i<input;i++) {
        if(input % i ==0  ) {
            input++;
            i=2;
        }
        else{
            continue;
        }
    }
    return input;
}

推荐答案

public int nextPrime(int input){
  int counter;
  input++;
  while(true){
    int l = (int) sqrt(input);
    counter = 0;
    for(int i = 2; i <= l; i ++){
      if(input % i == 0)  counter++;
    }
    if(counter == 0)
      return input;
    else{
      input++;
      continue;
    }
  }
}

无需检查取决于输入数字。检查一个数字的平方根就足够了。抱歉，我不记得定理名称。在这里，我们增加下一个素数的输入。

There is no need to check up on input number. It is enough to check up to the square root of a number. Sorry, I didn't remember the theorem name. Here we are incrementing the input for next prime.

此解决方案的时间复杂度O（n ^（3/2））。

The time complexity of this solution O(n^(3/2)).

这篇关于查找下一个质数的最佳方法（Java）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！