Prime numbers

Java 21.1.2011 No Comments

A natural number is called a prime number (or a prime) if it is bigger than one and has no divisors other than 1 and itself.

Prime number, Wikipedia

The assignment here is to calculate all prime numbers less than 100.

The solution provided uses the following to determine if a given number is prime.

• 2 is prime
• Any number divisible by 2 is not prime
• If the number is divisible by any odd number then it is not prime
• Otherwise it is prime

Notice the use of Modulus operator (%) to determine if a number is divisible by another number. This operator returns the remainder of the division of two number. eg. 19 % 4 = 3 (19 / 4 = 4 remainder 3)

package com.learnjava.math;

/**
* Write a Java program that calculates all
* prime numbers less than 100.
*
* @author http://learn-java-by-example.com
*
*/

public class PrimeNumbers {

public static boolean isPrime(int n) {
if (n==2) {

// 2 is a prime
return true;

} else if (n%2 == 0) {

// even numbers are not prime
// (they are divisible by 2)

return false;

} else {

// Now test all possible odd divisors
// less than square root of n

// Take the square root

int s = (int) Math.sqrt(n);

// Loop through odd divisors 3, 5, ....

for (int i=3; i<=s; i+=2) {
if (n % i == 0) {

// if n is divisible by i then is is not prime

return false;
}
}

// If we get to here then n must be a prime

return true;
}
}

public static void main(String[] args) {
System.out.println("Prime numbers:");

for (int n = 2; n < 100; n ++) {
if (isPrime(n)) {

// n is prime
System.out.println(n);
}
}
}
}

The solution provided here is quite inefficient and only really suitable for calculating small primes. More efficient solutions will be presented in future posts.