Question

6.25 (Prime Numbers) A positive integer is prime if it’s divisible by only 1 and itself. For example, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not. The number 1, by definition, is not prime. a) Write a method that determines whether a number is prime. b) Use this method in an application that determines and displays all the prime numbers less than 10,000. How many numbers up to 10,000 do you have to test to ensure that you’ve found all the primes? c) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number n is prime, but you need only go as high as the square root of n. Re- write the program, and run it both ways.

Answer 1

Answer:

1. public class Main {
3.    public static void main (String [] args) {
5.        for(int i = 2; i < 10000; i++){
6.            if(isPrime1(i)){
7.               System.out.print(i + " ");
8.            }
9.        }
11.        System.out.println();
13.        for(int i = 2; i < 10000; i++){
14.            if(isPrime2(i)){
15.                System.out.print(i + " ");
16.            }
17.        }
18.    }
20.    public static boolean isPrime1(int n){
21.      
22.        for(int i=2; i <= n/2; i++){
23.            if(n % i  == 0){
24.                return false;
25.            }
26.        }
28.        return true;
29.    }
31.    public static boolean isPrime2(int n){
33.        for(int i=2; i <= Math.sqrt(n); i++){
34.            if(n % i  == 0){
35.                return false;
36.            }
37.        }
39.        return true;
40.    }
41. }

Explanation:

Firstly, create the first version of method to identify a prime number, isPrime1. This version set the limit of the for loop as n/2. The for loop will iterate through the number from 2 till input n / 2 and check if n is divisible by current value of i. If so, return false to show this is not a prime number (Line 22 - 26). Otherwise it return true to indicate this is a prime number.

In the main program, we call the isPrime1 method by passing the i-index value as an argument within a for-loop that will iterate through the number 2 - 10000 (exclusive).  If the method return true, print the current i value). (Line 5 - 9)

The most direct way to ensure all the prime numbers below 10000 are found, is to check the prime status from number 2 - 9999 which is amount to 9998 of numbers.

Next we create a second version of method to check prime, isPrime2 (Line 31 - 40). This version differs from the first version by only changing the for loop condition to i <= square root of n (Line 33).  In the main program, we create another for loop and  repeatedly call the second version of method (Line 13 - 17). We also get the same output as in the previous version.