Prime Number Program in Java, simple program giving headache to me

• 12-13-2013, 09:31 PM
immohan
Prime Number Program in Java, simple program giving headache to me
hi friends,

First of all am new to programming,
while leaning some java program online i came across to this below Program.
Code:

```import java.util.*;   class PrimeNumbers {   public static void main(String args[])   {       int n, status = 1, num = 3;         Scanner in = new Scanner(System.in);       System.out.println("Enter the number of prime numbers you want");       n = in.nextInt();         if (n == 1)       {               System.out.println("First prime number is :-");         System.out.println(2);       }             else if (n > 1)       {         System.out.println("First "+n+" prime numbers are :-");         System.out.println(2);             }       else       {         System.out.println("Enter the Valid Number");       }           for ( int count = 2 ; count <=n ;  )       {         for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )         {           if ( num%j == 0 )             {                 status = 0;               break;             }         }         if ( status != 0 )         {             System.out.println(num);             count++;         }         status = 1;         num++;       }          } }```
Program is working fine
Enter the number of prime numbers you want
5
First 5 prime numbers are :-
2
3
5
7
11

Code:

```for ( int count = 2 ; count <=n ;  )       {         for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )         {           if ( num%j == 0 )             {                 status = 0;               break;             }         }         if ( status != 0 )         {             System.out.println(num);             count++;         }         status = 1;         num++;       }          }```
somebody please explain this loop am really not getting the answer, how does it works, am trying it for two days really unable to get the answer please somebody help me..........

how this loop code working even i tried by working the loop in paper but not getting the answer
• 12-13-2013, 10:19 PM
jim829
Re: Prime Number Program in Java, simple program giving headache to me
The outer loop simply iterates until the number of required primes has been met. The inner loop simply divides the test case by numbers from 2 to the square root of the test case. If all remainders are non-zero, then the test case is a prime and the count is updated.

Regards,
Jim
• 12-14-2013, 09:00 AM
immohan
Re: Prime Number Program in Java, simple program giving headache to me
Quote:

Originally Posted by jim829
The outer loop simply iterates until the number of required primes has been met. The inner loop simply divides the test case by numbers from 2 to the square root of the test case. If all remainders are non-zero, then the test case is a prime and the count is updated.

Regards,
Jim

hi friend,

Thanks for your response

sorry to say its not clear yet (the inner loop)

Code:

```for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )         {           if ( num%j == 0 )             {                 status = 0;               break;             }```
how its working friend, it showing two types of behaviour.
if you have time please explain me friend
• 12-14-2013, 09:15 PM
jim829
Re: Prime Number Program in Java, simple program giving headache to me
The % operator gives a remainder. So if num % j == 0 then j divides into num evenly so there is no remainder and thus num is not a prime. Once a zero remainder is detected, status is set to 0 and the loop breaks out. If, however, for the entire loop the status is never set to a 0, then the number must be a prime since no other numbers (j) divided it.

Regards,
Jim
• 12-14-2013, 09:39 PM
JosAH
Re: Prime Number Program in Java, simple program giving headache to me
... and please replace that loop condition by 'j*j <= num', it's cheaper ...

kind regards,

Jos
• 12-15-2013, 12:20 AM
jim829
Re: Prime Number Program in Java, simple program giving headache to me
It seems that j*j is computed for each iteration of the inner loop so as num gets larger, the computation time of j*j might exceed the call of the sqrt function. Especially if the Math.sqrt(num) is hoisted out of the loop (either manually or by the compiler).

Regards,
Jim
• 12-15-2013, 07:40 AM
JosAH
Re: Prime Number Program in Java, simple program giving headache to me
Quote:

Originally Posted by jim829
It seems that j*j is computed for each iteration of the inner loop so as num gets larger, the computation time of j*j might exceed the call of the sqrt function. Especially if the Math.sqrt(num) is hoisted out of the loop (either manually or by the compiler).

In the code above, Math.sqrt(num) is computed as many times as j*j would be computed; of course there are many more optimizations possbile here; b.t.w. a single multiplication can never be more expensive than a square root computation, especially when j*j <= n.

kind regards,

Jos