CODEWITHSUNDEEP
java
Vignesh Vicky
Vignesh Vicky

Reputation: 31

program logic of printing the prime numbers

Can any body help to understand this java program?

It just prints prime numbers, as you enter how many you want and it works well.

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 "+n+" prime numbers are :-");
         System.out.println(2);
       }

       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++;
      }         
   }
}

I don't understand this for loop condition

for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )

why we are taking sqrt of num...which is 3....why we assumed it as 3?

Upvotes: 0

Views: 5463

Answers (7)

mohan1989
mohan1989

Reputation: 1

public class PrimeNumber {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    ArrayList a = new ArrayList();
    for (int i = 1; i <= 100; ++i) {
        if (isPrime(i))
            a.add(i);
    }
    System.out.println("List : " + a);

}

public static boolean isPrime(int value) {
    if (value <= 1)
        return false;


    if ((value % 2) == 0)
        return (value == 2);

    for (int i = 3; i <= value - 1; i++) {
        if (value % i == 0) {
            return false;             
        }
    }     

    return true;
}

}

Upvotes: -1

assylias
assylias

Reputation: 328619

Imagine that n can be divided by a number k that is greater than sqrt(n). Then you have:

n = k * j

where j is a number which must be less than sqrt(n) (if both k and j are greater than sqrt(n) then their product would be greater than n).

So you only need to find the divisors that are less than or equals to sqrt(n) and you can find those that are greater than or equals to sqrt(n) by a simple division. In my example, once you have found j, you can find k = n / j.

Upvotes: 2

Ravitheja
Ravitheja

Reputation: 142

A quick but dirty solution..

import java.util.Scanner;

class testing
{
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        int n, i, j, count = 1;
        System.out.print("How many Numbers ? : ");
        n = input.nextInt();
        for(j = 1;count<=n;j++)
        {

            if(j==1 || j==2)
            {
                System.out.println(j);
                count++;
                continue;
            }
            for(i=2;i<=j/2;i++)
            {
                if(j%i==0)
                    break;
                else if(i == j/2 && j%i != 0)
                {
                    System.out.println(j);
                    count++;
                }  
            }
        }       
    }
}

Upvotes: 0

Sanchit
Sanchit

Reputation: 2260

The line in question is basically trying to find numbers that are factors of your given number (and eliminating them as not-primes). If you find no factors of a given number then you can say that the number is prime.

As far as finding factors goes, you only need to go up to sqrt(N) because if you go any higher you are looking at numbers you have already seen before. This is because every time you find a factor you actually find two factors. If a is a factor of N then N/a and a are both factors of N.

Upvotes: 1

Aditya
Aditya

Reputation: 5619

The factor of a number can lie only from 1 to sqrt of num. So instead of checking from 1 till num for its factors, we check for all numbers from 1 to sqrt(num) so see if any of them divides num. If any divides num, it is not prime, else it is. This improves efficiency of code.

Upvotes: 0

sailingthoms
sailingthoms

Reputation: 948

If I'm right there is a theory in math, saying that nearly all prime numbers can be determined when checking numbers from 2 to square root of n instead of checking all numbers from 2 to n oder 2 to n/2.

Upvotes: 0

Paul
Paul

Reputation: 27433

A number N is prime if the only integers that satisfy N = A*B are 1 and N (or N and 1).

Now to check a number N as prime we could search all A from 2 to N and B from 2 to N, to see if N=A*B. That would take O(N^2) time, and is really inefficient.

It turns out that we only need to divide N by a number and see if there is a remainder. This brings it down to O(N).

And further, we don't need to check all the way from A=2 to A=N. If A is greater than sqrt(N), then B must be less than sqrt(N). Therefore we only need to check A from 2 to sqrt(N) to see if N/A has a remainder.

Upvotes: 0

Related Questions