0

I am currently working on making a sieve for school. Here is my code so far: 

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

Because this involves many loops, I know that this method will not be efficient or have high runtimes for bigger inputs. However, how would I find the average runtime (in Big O) of my current code so far?

Henry Wang
  • 161
  • 2
  • 2
  • 14
  • https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity – Andy Turner Dec 14 '18 at 14:47
  • Maybe try this: https://stackoverflow.com/questions/1210081/checking-run-time-in-intellij-idea If you use Intellij you can install the VisualVM plugin to check for the runtimes or you can use the other methods that are outlined in the post above. – Johnston Liu Jun 10 '19 at 02:38
  • Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – tkruse Jun 10 '19 at 03:35

0 Answers0