Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
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?

share|improve this question
add comment

4 Answers 4

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();
share|improve this answer
    
I have already implemened Runnable , that point is moot –  Computernerd Jun 9 at 15:22
    
Agreed; edited answer to remove that comment. The point about Thread management stands. –  VoiceOfUnreason Jun 9 at 15:37
add comment

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.");
    }
  }
}
share|improve this answer
    
The algorithm can be made faster by skipping multiplies of 2, and so on, but the basic idea remains the same. –  fajarkoe Jun 9 at 14:59
1  
There are a few compromises to be made. Eratosthenes sieve is much faster, but also uses much more memory. Additionally Eratosthenes sieve is slower in the beginning and faster towards the end, so you gotta know beforehand, how many numbers you need to consider. I don't think Eratosthenes sieve becomes much faster by skipping multiples of 2, because that is more or less built into the algorithm from the start, but you could save some memory that way. –  kasperd Jun 9 at 15:25
    
@kasperd He means, increment the counter by two each time, so it doesn't even have to check even numbers. –  AJMansfield Jun 10 at 21:22
    
@AJMansfield Increasing i by two each time is not going to save any significant amount of time, because most time is spent in the inner loop, which is only executed once a prime has been found. Increasing j by two each time could speed up the algorithm, but it requires a few other changes to still get the correct result. –  kasperd Jun 10 at 21:51
add comment

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;
share|improve this answer
add comment

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;
}
share|improve this answer
    
Although I'd cache the square root, and convert it to an int, to avoid repeatedly performing extra computations. –  AJMansfield Jun 10 at 21:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.