How To Calculate Prime Numbers In Java

image credit:www.brooksdesign-ps.net
As per wiki here a prime no is--" A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because only 1 and 5 evenly divide it, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6. The fundamental theorem of arithmetic establishes the central role of primes in number theory: any integer greater than 1 can be expressed as a product of primes that is unique up to ordering. The uniqueness in this theorem requires excluding 1 as a prime because one can include arbitrarily many copies of 1 in any factorization, e.g., 3, 1 × 3, 1 × 1 × 3, etc. are all valid factorizations of 3."

So the logic we will follow is "check if the remainder for the number with the other number excluding 1,and the number should always have some value. else it is not a valid Prime number.


How the main method will be


public class PrimeNumber {
 public static void main(String[] args) {
//if you are going to check with a upper limit
  int num=100;
  for(int i=2;i<num;i++  )
  {
   calculatePrimi(i);
   
  }
//One more way to get no from user...
calculatePrimi(Integer.parseInt(JOptionPane.showInputDialog(null, "Please enter your Number here")));
calculatePrimi(getNumber());
 }

The function will look like---

 public static void calculatePrimi(int i)
 {
  //this will take some integer value
  boolean isPrime=false;
  //making it false initially
  for(int j=2;j<i;j++  )
  {
   //our counter will run from 2 to number-1
  if(i%j==0)
  {
   isPrime=false;
   break;
   
  }
  else{
   isPrime=true;
  }
   
  }
  if (isPrime==true)
  {
   System.out.println("The number " +i " is a prime Number");
  }
  else
  {
   System.out.println("The number " +i "is a Not prime Number");
  }
 }
 
Let us get the number from user to test if that is a valid prime no



 public static int getNumber()
 {
  int st=0;
  try{
     //take some number from user
     st=Integer.parseInt(JOptionPane.showInputDialog(null, "Please enter a valid Number here"));
     System.out.println(st);
  }
  catch(Exception e)
  {
   System.out.println(e);
   getNumber();
  }
 return st;
 }
 


Optimization : The above logic works well for small range or if the number is small enough. if we deal with a very big prime number then the above code will keep evaluating from 2 to that big number. This put burden on processor. The below logic is applied on the prime number calculation to reduce the complexity and increase the efficiency.
Logic the for loop must not go till the number. It should go till the square root of that number. So for any number the possible divisor can be found between 2 to square root of that number.for square root we can use Math.sqrt(int a) function. This function returns double so we need to cast it to int.

public class CalculatePrime{
public static void main(String args[])
{
System.out.println(isPrime(1000));
}
public static boolean isPrime(int n) {
for (int i = 2; i <= (int)Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
The output of the code:
$javac CalculatePrime.java
$java -Xmx128M -Xms16M CalculatePrime
false
How To Calculate Prime Numbers In Java How To Calculate Prime Numbers In Java Reviewed by Animesh Chatterjee on March 24, 2013 Rating: 5

2 comments:

  1. I could not :(( hope next time I will be able to (f)

    ReplyDelete
  2. No Problem Ghanku...better luck next time

    ReplyDelete

Powered by Blogger.