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.

Leave a Reply

s2Member®