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:

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.
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?

1/ yes. see about memoization, and go until sqrt(n), not n/2 2/ you are not using counter for anything else. replace counter ++ by return true altogether. if you reach the end of the loop, return false (also you call it counter and count. that would not work) — njzk2
– njzk2, Commented Aug 5, 2015 at 3:35

VoiceOfUnreason · Accepted Answer · 2014-06-09 15:37:38Z

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();

Agreed; edited answer to remove that comment. The point about Thread management stands. — VoiceOfUnreason
– VoiceOfUnreason, Commented Jun 9, 2014 at 15:37

fajarkoe · Accepted Answer · 2014-06-09 14:55:31Z

4

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.");
    }
  }
}

answered Jun 9, 2014 at 14:55

fajarkoe

1611 bronze badge

\$\begingroup\$ The algorithm can be made faster by skipping multiplies of 2, and so on, but the basic idea remains the same. \$\endgroup\$

fajarkoe
– fajarkoe

2014-06-09 14:59:49 +00:00
Commented Jun 9, 2014 at 14:59
1

\$\begingroup\$ 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. \$\endgroup\$

kasperd
– kasperd

2014-06-09 15:25:58 +00:00
Commented Jun 9, 2014 at 15:25
\$\begingroup\$ @kasperd He means, increment the counter by two each time, so it doesn't even have to check even numbers. \$\endgroup\$

AJMansfield
– AJMansfield

2014-06-10 21:22:28 +00:00
Commented Jun 10, 2014 at 21:22
\$\begingroup\$ @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. \$\endgroup\$

kasperd
– kasperd

2014-06-10 21:51:55 +00:00
Commented Jun 10, 2014 at 21:51
\$\begingroup\$ I usually write it int j = 2*i; j < end + 1; j+=i and isPrime[j] = false \$\endgroup\$

njzk2
– njzk2

2015-08-05 03:38:13 +00:00
Commented Aug 5, 2015 at 3:38

Add a comment |

kasperd · Accepted Answer · 2014-06-09 14:13:40Z

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;

answered Jun 9, 2014 at 14:13

kasperd

2771 gold badge4 silver badges14 bronze badges

Add a comment |

tohanov · Accepted Answer · 2014-06-09 23:14:28Z

0

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;
}

answered Jun 9, 2014 at 23:14

tohanov

1

1

\$\begingroup\$ Although I'd cache the square root, and convert it to an int, to avoid repeatedly performing extra computations. \$\endgroup\$

AJMansfield
– AJMansfield

2014-06-10 21:19:36 +00:00
Commented Jun 10, 2014 at 21:19

Add a comment |

Stack Exchange Network

isPrime Number Algorithm

4 Answers 4

You must log in to answer this question.

Hot Network Questions

isPrime Number Algorithm

4 Answers 4

You must log in to answer this question.

Related

Hot Network Questions