CODEWITHSUNDEEP
java
Minh Hoang
Minh Hoang

Reputation: 303

Java Prime Number need to be faster

import java.util.*;

public class PrimeNum {
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);     
    int a = input.nextInt();
    int b = input.nextInt();

    for(int i = a ; i <= b ; i++ ) {
        if ( i == 2 || i == 3 ) System.out.println(i);

        for(int j = 2; j <= (i / 2) ; j++ ) {
            if ( (i % j) == 0 ) break;
            if ( j == (i / 2) ) System.out.println(i);
        }
    }

}
}

This program is simple, type in 2 int a and b. It will find any Prime Number within a and b.

How can I make this faster ?. I tried the Math.sqrt one but it does not work well in this case :( I do not really know because whenever I use it, it causes a lot of bugs. I would love to see someone use Squareroot in this case.

Upvotes: 0

Views: 229

Answers (3)

Mark Byers
Mark Byers

Reputation: 838296

I agree with the suggestions to use a different approach, but I'll try to explain why your approach doesn't work.

I think the problem is in the way you are printing the result:

for(int j = 2; j <= (i / 2) ; j++ ) {
    if ( (i % j) == 0 ) break;
    if ( j == (i / 2) ) System.out.println(i);
}

This works fine for i / 2 but it will fail for Math.sqrt(i) because it is not always a whole number and then j == Math.sqrt(i) will never be true. Your code will only work when i is an exact square.

It would be better to refactor your code so that your primality test is in a separate method:

boolean isPrime(int i) {
    int s = (int)Math.sqrt(i);
    for (int j = 2; j <= s; j++) {
        if (i % j == 0) { return false; }
    }
    return true;
}

Upvotes: 2

Per Alexandersson
Per Alexandersson

Reputation: 2523

How about only checking odd numbers, since even numbers very rarely are primes...

if(a==2) System.out.println(2);
if((a%2)==0) a++;
for(int i = a ; i <= b ; i+=2 ) {
  if(i == 3 ) System.out.println(i);
  int root = (int) Math.sqrt(i);

  for(int j = 2; j <= root ; j+=2 ) {
      if ( (i % j) == 0 ) break;
      if ( j == root ) System.out.println(i);
  }
}

Upvotes: 0

lhlmgr
lhlmgr

Reputation: 2187

You can use this http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm. Its fast and simple to implement. Its not exactly the same, because you can not define a lowerbound (a) for that algorithm, but you can, after you found all elements from 2 to b, return just the numbers between a and b.

Upvotes: 0

Related Questions