[Solved] How can I find out if a number is prime or not without using division or modulus in Java?

Question

Here’s a way with nested loops (semi-pseudocode):

int x ;
//check if x is a multiple of any two factors < x
for (int i1 = 2 ; i1 < x ; i1++) {
    for (int i2 = i1 ; i2 < x ; i2++) {
        prod = i1 * i2 ;
        if (prod > x) break ;
        if (prod == x) return "x is not prime" ;
    }
}
return "x is prime" ;

This should be reasonably efficient, though for big numbers you’d want to improve it. One check you could do: if (i1 == i2 && prod > x) return "x is prime" That would eliminate a lot of iterations.

Accepted Answer

Here’s a way with nested loops (semi-pseudocode):

int x ;
//check if x is a multiple of any two factors < x
for (int i1 = 2 ; i1 < x ; i1++) {
    for (int i2 = i1 ; i2 < x ; i2++) {
        prod = i1 * i2 ;
        if (prod > x) break ;
        if (prod == x) return "x is not prime" ;
    }
}
return "x is prime" ;

This should be reasonably efficient, though for big numbers you’d want to improve it. One check you could do: if (i1 == i2 && prod > x) return "x is prime" That would eliminate a lot of iterations.