How To Calculate Prime Numbers In Java?

2
132
• 1
•
•
•
•
•
•
•
•
•
1
Share 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(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

Don't miss out!

Receive top technical news, lesson ideas, travel tips and more!

Give it a try. You can unsubscribe at any time.

• 1
•
•
•
•
•
•
•
•
•
1
Share

1. Ghanku