Prime number is a natural number greater than 1 and only divisible by 1 or itself, i.e. a prime number has only two factors, 1 and itself. The number 2 is the smallest and only even prime number. 1 is excluded as a prime number.

In order to check if a number is prime we should find if there is any divisor other than 1 or itself. We can find this by dividing the number(say n) by each number between 2 and n-1. For e.g. in order to check if 13 is a prime number, we need to check if 13 is divisible by 2 through 12. If remainder is 0 for any one division then the number is not prime.

Trying a number n by all numbers between 2 and n-1 is very time consuming, and luckily we have a faster approach. It is only necessary to

For e.g. if n=61, we need to test only the numbers between 2 and sqrt(61).

sqrt(61) = 7.

61 is not evenly divisible by 2,3,4,5,6,7, so 61 is a prime number.

Again, to further save time, we can

In order to check if a number is prime we should find if there is any divisor other than 1 or itself. We can find this by dividing the number(say n) by each number between 2 and n-1. For e.g. in order to check if 13 is a prime number, we need to check if 13 is divisible by 2 through 12. If remainder is 0 for any one division then the number is not prime.

Trying a number n by all numbers between 2 and n-1 is very time consuming, and luckily we have a faster approach. It is only necessary to

*in order to check a prime number.***test the factors between 2 and the square root of n**For e.g. if n=61, we need to test only the numbers between 2 and sqrt(61).

sqrt(61) = 7.

61 is not evenly divisible by 2,3,4,5,6,7, so 61 is a prime number.

Again, to further save time, we can

*from the list(2,3,4,5,6,7). For e.g. in the list (2,3,4,5,6,7), we should try with only the prime numbers 2,3,5,7.***test with only the prime factor****Sample Java program to check if a number is prime and print all prime numbers up-to the number:**```
package com.examples;
import java.util.Scanner;
public class PrimeNos {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter a number to check prime: " );
int n = in.nextInt();
if (checkPrime(n))
System.out.println("Number is prime");
else
System.out.println("Number Not prime....");
System.out.print("The prime numbers till " + n + ": ");
for (int i=2; i<=n;i++){
if (checkPrime(i))
System.out.print(i + " ");
}
}
public static Boolean checkPrime(int n) {
int sqt = (int) Math.sqrt(n);
for (int i=2; i<=sqt; i++) {
Boolean test = checkPrime(i); //save more time, use only prime factors
if (test) {
int result = n % i;
if (result == 0){
return false;
}
}
}
return true;
}
}
```

**Output:**```
Enter a number to check prime: 29
Number is prime
The prime numbers till 29: 2 3 5 7 11 13 17 19 23 29
```

## No comments:

## Post a Comment