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

Example Answer:

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

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

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

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

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

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

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