CODEWITHSUNDEEP
javabig-o
80s
80s

Reputation: 41

Calculate big O notation for prime numbers

import java.util.Scanner;
/**
Prints all prime numbers less than a given value
*/
public class PrimeNumberMethod {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.println("Enter a value for n: ");
    int n = input.nextInt();
    System.out.println("The prime numbers in the first " + n + 
     " numbers are ");
    printPrimeNumbers(n);
  }

  public static void printPrimeNumbers(int n) {
    final int NUMBER_OF_PRIMES_PER_LINE = 10; // Display 10 per line
    int count = 0; // Count the number of prime numbers
    int number = 2; // A number to be tested for primeness
    int runcount = 0;
    // Repeatedly find prime numbers
    while (number < n) {
      runcount++;
      if (isPrime(number)) {
        count++; // Increase the count

        if (count % NUMBER_OF_PRIMES_PER_LINE == 0) {
          // Print the number and advance to the new line
          System.out.printf("%-5s\n", number);
        }
        else
          System.out.printf("%-5s", number);
      }

      // Check if the next number is prime
      number++;
    }
    System.out.println("\n"+runcount);
  }

  /** Check whether number is prime */
  public static boolean isPrime(int number) {
    for (int divisor = 2; divisor <= number / 2; divisor++) {
      if (number % divisor == 0) { // If true, number is not prime
        return false; // number is not a prime
      }
    }

    return true; // number is prime
  }
}

My friend and I have been trying to calculate the big O notation for a while now but we're lost. We know the notation of the outer loop is O(n) but what is the inner loop? And what's the big O notation for the program overall, we think it's O(n) because that's the largest loop in the algorithm.

Upvotes: 1

Views: 240

Answers (1)

Arthur Tondereau
Arthur Tondereau

Reputation: 86

For each round of the loop you check if the number is prime with your isPrime function, which is O(n). Doing that for every round will make your overall complexity O(n^2).

Upvotes: 2

Related Questions