java - 埃拉托色尼筛的运行时

Question

我目前正在为学校做一个筛子。到目前为止，这是我的代码：

public static List<Integer> sieve(int input) {
    int[] numbers = new int[input - 2 + 1];
    int prime = 2; 
    // start of with 2 since first prime w/ specific multiples
    int counter = 0;
    for (int i = prime; i <= input; i++) {
      numbers[counter] = i;
      counter++;
    }

    // Main sieve logic: remove all multiples of that number (except itself), move onto next number in ArrayList (which must be prime)

  for (int x = 0; x < numbers.length; x++) {
    for (int j = findIndex(numbers, prime) + 1; j < numbers.length; j++) {
      if (numbers[j] % prime == 0) {
        numbers[j] = 0;
      } 
    }


    for (int k = findIndex(numbers, prime) + 1; k < numbers.length; k++) {
      if (numbers[k] != 0) {
        prime = numbers[k];
        break;
      }
    }

  }



    pushZerosToEnd(numbers, numbers.length);

    List<Integer> cleanerResult = new ArrayList<>();

    for (int y = 0; y < numbers.length; y++) {
      if (numbers[y] != 0) {
        cleanerResult.add(numbers[y]);
      }
    }

    return cleanerResult;
  }

// Assume that pushZerosToEnd() and findIndex() do their specified action

因为这涉及许多循环，所以我知道这种方法效率不高，或者对于更大的输入来说运行时间很长。但是，到目前为止，我如何找到当前代码的平均运行时间（在 Big O 中）？

标签： javasieve