printing Prime numbers in java

Question

This Java code prints out prime numbers between 2-100.

And this works fine.

This code is not done by me.

But I am trying to figure out what is happening with this code.

Can anyone tell me what is happening after the second (for) loop?

class primenumbers{
    public static void main(String args[]) 

    {    
        int i, j; 
        boolean isprime; 

        for(i=2; i < 100; i++) { 
            isprime = true;  

            // see if the number is evenly divisible 
            for(j=2; j <= i/j; j++) 
                // if it is, then its not prime 
                if((i%j) == 0) isprime = false; 

            if(isprime) 
                System.out.println(i + " is prime."); 
        }
    }
}

Answer 1

The first loop just for generating numbers from 2 to 100.

The second loop tries to find if the number is divisible by any other number. Here we try to divide a the number with a set of numbers (2 to prime_index).

Let's say the number is 10, the prime index is 10/2 = 5 for first iteration(j = 2). Which means, if the number 10 is not divisible by any number between 2 and 5, it's a prime number. It's divisible by 2 itself making it a non prime number.

Let's say the number is 9, now the prime index is 9/2 = 4 for first iteration(j = 2). Now, 9 % 2 gives 1 as reminder. So, loop continues for second iteration (j = 3). Now the prime index is 9/3 = 3 (Note here the prime index value is reduced from 4 to 3) So, now if the number is not divisible by 3, its decided as a prime number.

So, for every iteration, the prime index will reduce, making the number of iterations reduced.

Example for Number 97,
j = 2, prime index = 97/2 = 48 (no of iterations for loop)
j = 3, prime index = 97/3 = 32 (no of iterations for loop)
j = 4, prime index = 97/4 = 24 (no of iterations for loop)
j = 5, prime index = 97/5 = 19 (no of iterations for loop)
j = 6, prime index = 97/6 = 16 (no of iterations for loop)
j = 7, prime index = 97/7 = 13 (no of iterations for loop)
j = 8, prime index = 97/8 = 12 (no of iterations for loop)
j = 9, prime index = 97/9 = 10 (no of iterations for loop)
j = 10, prime index = 97/10 = 9 (loop exits as condition failed 10 <= 9 and declares 97 as a prime number)

Now, here the loop actually took 10 iterations instead of the proposed 48 iterations.

Let's modify the code for better understanding.

public static void main(String args[]) {    
        // Number from 2 to 100
    for(int i=2; i < 100; i++) { 
       if (isPrimeNumber(i)) {
            System.out.println(i + " is prime");
       }
    }
}

Now, lets see a method isPrimeNumberNotOptimized() which is not optimized.

private static boolean isPrimeNumberNotOptimized(int i) {
    for(int j=2; j <= i/2; j++) {
        // if it is, then its not prime 
        if((i%j) == 0) {
            return false;
        }
    }
    return true; 
}

And, another method isPrimeNumberOptimized() which is optimized with prime index.

private static boolean isPrimeNumberOptimized(int i) {
    for(int j=2; j <= i/j; j++) {
        // if it is, then its not prime 
        if((i%j) == 0) {
            return false;
        }
    }
    return true; 
}

Now, both methods will run and print the prime numbers correctly.

But, the optimized method will decide 97 is a prime number at 10th iteration.

And, the non-optimized method will decide the same in 48th iteration.

Hope, you understand it now.

FYI: prime index is the number we used for calculation. Such that if a number is not divisible between 2 & the derived prime index, its a prime number

Answer 2

Outer (first) loop enumerates all numbers in [2,100).

Inner (second) loop checks if a current number from the first loop is dividable by anything.

This check is done using % (remainder): (i%j)==0 when remainder of division i by j is 0. By definition when remainder is zero i is dividable by j and therefore is not a prime : isprime=false.

---

You only need to check in [2,i/j] because you only need to check up to sqrt(i) (explanation in the last section).

Having said that the inner loop can be re-written as:

...
int s = sqrt(i);
for(j=2; j <= s; j++)
...

however sqrt is more expensive than division, therefore it's better to rewrite j<=sqrt(i) as (squaring both sides) j^2 < i and j*j<i and j<i/j. When j is big enough j*j might overflow therefore both sides were divided by j in the final step.

---

Explanation of sqrt(i) taken from here: Why do we check up to the square root of a prime number to determine if it is prime?

if i is not prime, then some x exists so that i = x * j. If both x and j are greater than sqrt(i) then x*j would be greater than i.

Therefore at least one of those factors (x or j) must be less than or equal to the square root of i, and to check if i is prime, we only need to test for factors less than or equal to the square root.

Answer 3

This is a modification of the Sieve of Eratosthenes.

First, I'll just summarize what the sieve of Eratosthenes does, you can skip to the last paragraph if you already know this. The sieve of Eratosthenes algorithm loops through a certain boundary of numbers. (Say 2 - 100). For every number it loops through, it cancels out multiples, for example, since 2 is a prime number (true), all multiples of 2 are not (They are false). Same for 3, 5, and so on; and the algorithm skips every predetermined non-prime number. Therefore, a simulation of the algorithm would be:

2 ---prime number... cancels out 4, 6, 8, 10, 12....
3 ---prime number... cancels out 6, 9, 12, 15, 18...
4 --- ALREADY CANCELLED OUT... Skip
5 --- prime number... cancels out 10, 15, 20, 25...
6 --- ALREADY CANCELLED OUT... Skip

The numbers not cancelled are therefore the prime numbers. You can also read this for more information: http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Now, to your question, your algorithm loops through the list of numbers. For each number(say x), it checks if any of the previous numbers looped through (i / j) is a factor of the x. The reason why i/j is used as the boundary for the second for loop is for efficiency. If you're checking if 10 (for example) is a prime number, there's no need to check whether 6 is a factor. You can conveniently stop at n/(n/2). That's what that part is trying to achieve.

Answer 4

public class PrimeNumber {

//check prime number
public static boolean prime(int number){
    boolean isPrime=true;

    for(int i=number-1;i>1;i--){

        if(number%i==0){
            isPrime=false;
            System.out.println(i);
            break;
        }
    }

   return isPrime;
}

public static boolean getPrimeUsingWhile(int number){
    boolean isPrime=true;
    Integer temp=number-1;
    while (temp>1){

        if(number%temp==0){
            isPrime=false;
            break;
        }

        temp--;
    }

    return isPrime;
}
//print primenumber given length
public static List<Integer> prinPrimeList(){

    boolean isPrime=true;
    List<Integer> list=new ArrayList<>();
    int temp=2;
    while (list.size()<10){

        for(int i=2;i<temp;i++){

            if(temp%i==0){
                isPrime=false;
                break;
            }else{
                isPrime=true;
            }

        }

        if(isPrime){list.add(temp);}
        temp++;
    }


    return list;
}


public static void main(String arg[]){

    System.out.println(prime(3));
    System.out.println(getPrimeUsingWhile(5));
    System.out.println(Arrays.toString(prinPrimeList().toArray()));
}

}