isPrime Number Algorithm

Question

public class RunnableThreadPrimeNumber implements Runnable
{
    private long startNum;
    private long endNum;
    private Thread t;



RunnableThreadPrimeNumber(long start , long end )
{
        t = new Thread(this);
        this.startNum = start;
        this.endNum = end;

        t.start();
}

public void run()
{
    for ( int i = start ; i <= last ; i++)
    {
        if (isPrime(i) == true)
        {
            System.out.println(i + " is prime")
        }

    }


}

private boolean isPrime(long n)
{
    int counter = 0;

    for (int i = 2 ; i < n / 2 ; i++)
    {
        if ( n % i == 0 )
        {
            counter ++;
        }
    }

    if ( count > 0 )
    {
        //number is prime
        return true;
    }
    else
    {
        //number is not prime
        return false;
    }

}

public static void main(String[] args)
{
    RunnableThreadPrimeNumber(2000,4000);
    RunnableThreadPrimeNumber(4001,6000);
}

}

Questions:

1. Is there any way to improve this algorithm which checks if a given number is prime? The improvement can be anything from space to running time complexity.

2. For my function isPrime(long n), I am currently looping through every possible number less than half the input number and returning true or false only after the for loop has finished.

   I am thinking of adding an addition if statement in the for loop which checks if the variable counter is greater than 0. If it's greater than 0, immediately return true. The advantage to this approach is that for some numbers, I can immediately return true/false without needing to finish the for loop. However, the cost comes at adding an additional if statement for every iteration in the for loop.

   How should I go about deciding if the additional if statement is worth the cost?

Answer 1

Code review:

As a rule, it's almost never a good idea to create your own thread directly - better to let an ExecutorService do the thread management for you.

if (isPrime(i) == true)

should be written

if (isPrime(i))

similarly

if ( count > 0 )
{
    //number is prime
    return true;
}
else
{
    //number is not prime
    return false;
}

should be

return count > 0 ;

You should also write some tests, since this condition looks backwards.

But for this specific case, kasperd has the right idea - you don't care how many different factors that the number has, just whether or not it is prime; early exit is the right answer here.

It would improve the code to separate the calculation from the reporting.

interface PrimeListener {
    void onPrime(long prime);
}

class TrivialPrimeListener implements PrimeListener {
    private final PrintStream out;

    TrivialPrimeListener (PrintStream out) {
        this.out = out;
    }

    TrivialPrimeListener () {
        this(System.out);
    }


    void onPrime(long prime) {
        // Even better would be to make this flexible about where it
        // sends t
        out.println(prime + " is prime");
    }
}

Then your loop would look like:

for ( long primeCandidate = start ; primeCandidate <= last ; primeCandidate++)
{
    if (isPrime(primeCandidate))
    {
        this.listener.onPrime(primeCandidate);
    }

}

And your initialization code would look something like

    this.startNum = start;
    this.endNum = end;
    this.listener = new TrivialPrimeListener();

Answer 2

You can also use Sieve of Eratosthenes algorithm. It runs much faster than your algorithm. The algorithm looks something like:

public static void main(String[] args) {
  int start = //
  int end   = //

  boolean[] isPrime = new boolean[end + 1];

  for (int i = 2; i < end + 1; i++) {
    isPrime[i] = true;
  }

  for (int i = 2; i < end + 1; i++) {
    if (isPrime[i]) {
      for (int j = 2; i * j < end + 1; j++) {
        isPrime[i * j] = false;
      }
    }
  }

  for (int i = start; i < end + 1; i++) {
    if (isPrime[i]) {
      System.out.println(i + " is prime.");
    }
  }
}

Answer 3

The algorithm will be a lot faster, if you write the loop as for (int i = 3 ; i*i <= n ; i += 2) and you return false from inside the loop as soon as you know the number is not a prime. Then you don't need the counter variable. If you get to the point after the loop, you know the number is prime.

That approach will break a few cases, so you need to start with the obvious cases before starting the loop:

if (n < 4) return n > 1;
if ((n % 2) == 0) return false;

Answer 4

You can change your isPrime function to go only through the numbers lower or equal to the square root of your n number. You can also immediately return false from the loop to save on runtime.

private boolean isPrime(long n)
{
    for (int i = 2 ; i <= Math.sqrt(n) ; i++)
    {
        if ( n % i == 0 )
        {
            return false;
        }
    }

    return true;
}