” 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 https://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.