Try to divide the number with sequential integers starting with two. As soon as a divisor is found, return false.
The algorithm can be greatly improved (see exercises), but let's implement it as above.
This program asks the user for an integer and then says if it is prime or composite. Trial divisors are used starting at two and going upward.
If a number is composite, then it equals a product N*M.
So N mod M == 0.
The program tests this for each trial divisor
An obvious improvement is that if the number is even, it is composite, so immediately return false. Otherwise, there is no need to test if any multiple of two divides the number. So, after testing if the number is even, start the trial divisor at three and increment by two each iteration.
Another great improvement is to observe that the trial divisors need not be any larger than the
square root of the number, since if the number equals the product N*M,
one of N or M must be smaller than or equal to the square root.
Making these two changes will enormously speed up the program. These improvements are left for the exercises.
If you run the program with a large prime it will run for a very long time. Try:
71755440315342536873
import java.math.BigInteger;
import java.util.Scanner;
class PrimeTester
{
public static Boolean isPrime( BigInteger N )
{
BigInteger trial;
trial = new BigInteger( "2" );
while ( trial.compareTo( N ) < 0 )
{
if ( N.remainder(trial).equals( BigInteger.ZERO ) )
return false;
trial = trial.add( BigInteger.ONE );
}
return true;
}
public static void main ( String[] args )
{
Scanner scan = new Scanner( System.in );
String input;
BigInteger suspect, trial;
System.out.print("Suspected Prime: ");
input = scan.next();
suspect = new BigInteger( input.trim() );
if ( isPrime( suspect ) )
System.out.println("This is a prime" );
else
System.out.println("This is a composite" );
}
}
C:> java PrimeTester
Suspected Prime: 2147483647
This is a prime
What do you suppose the following prints?
BigInteger A = new BigInteger( "2" ); BigInteger B; B = A.pow( 8 ); System.out.println( "B: " + B );