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

*Related*