Friday, April 13, 2012

Java Program to print Prime numbers in Java - Example Tutorial and Code

How to print Prime numbers in Java or how to check if a number is prime or not is classical Java programming questions, mostly taught in Java programming courses. A number is called prime number if its not divisible by any number other than 1 or itself and you can use this logic to check whether a number is prime or not. This program is slightly difficult than printing even or odd number which are relatively easier Java exercises. This Simple Java program print prime number starting from 1 to 100 or any specified number. It also has a method which checks if a number is prime or not.

This Java tutorial is in conjunction with my earlier tutorial for beginners like How to set Path in Java on windows and Unix , Java Program to reverse String in Java with recursion and recently  how to read file in Java etc, if you haven’t read them you may find them useful.


Code Example to print Prime numbers in Java

Here is complete sample code example to print prime numbers from 1 to any specified number. This Java program can also check if a number is prime or not as prime number checking logic is encapsulated in isPrime(int number) method.

import java.util.Scanner;

/**
 * Simple Java program to print prime numbers from 1 to 100 or any number.
 * A prime number is a number which is greater than 1 and divisible
 * by either 1 or itself.
 */

public class PrimeNumberExample {

    public static void main(String args[]) {
     
     //get input till which prime number to be printed
      System.out.println("Enter the number till which prime number to be printed: ");
      int limit = new Scanner(System.in).nextInt();
   
      //printing primer numbers till the limit ( 1 to 100)
      System.out.println("Printing prime number from 1 to " + limit);
      for(int number = 2; number<=limit; number++){
          //print prime numbers only
          if(isPrime(number)){
              System.out.println(number);
          }
      }

    }

    /*
     * Prime number is not divisible by any number other than 1 and itself
     * @return true if number is prime
     */

    public static boolean isPrime(int number){
        for(int i=2; i<number; i++){
           if(number%i == 0){
               return false; //number is divisible so its not prime
           }
        }
        return true; //number is prime now
    }
}

Output:
Enter the number till which prime number to be printed:
20
Printing prime number from 1 to 20
2
3
5
7
11
13
17
19


How to find if number is prime or not in JavaIn this Java program we have two part, first part which is taking input from user to print prime numbers and other part is function isPrime(int number) which checks whether a number is prime or not. Java method isPrime(int number) can also be used anywhere in code because its encapsulated logic of checking prime number. There is also another popular Java question is "How to check if a number is prime or not?", isPrime() can be used there.  its rather simple and just implement the logic of prime number in Java i.e. divides a number, starting from 2 till the number itself, if its divisible by another number means its not prime.

That's all on how to print prime numbers in Java or how to check if a number is prime or not. Its worth remembering logic that when a number is prime and how do you check for prime number. If you are doing homework then get an Idea but type the program yourself , that will give you thinking time on how this Java program is working and checking for prime numbers.

Related Java Program tutorials

30 comments :

Anonymous said...

There are many better ways of improving its complexity. This code has the worse case complexity

Javin @ select example in SQL said...

@Anonymous, Thanks for your comment. I think its much easier to understand as it co related with how you check for prime numbers in maths. would be great if you could share concrete example.

Rafal Sawicki said...

You don't need to loop from 2 to number to check if it's divisible, you only need to do that from 2 to sqrt(number).

Anonymous said...

In order to check if a number N is prime or not; it is enough to check if the number is divisible by any number from 2 to SQRT(N). If it is divisible then it is not a prime number else it is a prime number.
No need to check till (N - 1). This way you can improve time complexity of your code which is very important if the number N is huge. Say you have to generate 1st one million prime numbers.

Javin @ compareTo in Java Example said...

@Anonymous and @Rafal, I got it what you are saying.Indeed its enough to check between 2 and √n to confirm whether a number is prime or not. Thanks for pointing this.

Shweta said...

One good example of prime numbers in Java is hashcode(). hashcode() uses prime number as multiplier in order to generate uniform and unique hashcode.

Anonymous said...

few more question
how to determine prime numbers in Java
java prime number, prime number java example, how to check prime numbers in Java, how to find prime numbers in Java, how to print prime numbers in Java. how to calculate prime numbers in Java. Write a program to display prime numbers in Java. write a program to check if a number is prime or not.

Bisvas said...

I remember those days when programs like check if number is even or odd, prime, armstrong or perfect square were popular. now days programmer doesn't pay much attention over programming but rather they just want to learn more and more languages and technology like Java, C++, JSP, ASP etc etc. If you asked them to write program they fail to do in any language because they just familiar with syntax not even with complete library.

Mirec Z said...

only better thing than java program is C++ program... :o)
obviously in both cases I mean "well written" program... ;o)

Hima P said...

There are many better ways of improving its complexity. This code has the worse case complexity

semenoh said...

Also you dont need to check each number. If you can not devide by 2 you can skeep even numbers:
if (a % 2 == 0)
return false;
for (int i = 3; i < Math.sqrt(n); i+=2)
if (a % i == 0)
return false;
return true;

Anonymous said...

This is the worst way to check primality. Use Fermat's little theorem which is easiest of the better algorithms like Miller–Rabin primality test and Solovay–Strassen primality test.

Javin @ Sort HashMap by values in Java said...

@Anonymous, Thanks for sharing those useful algorithm for checking prime numbers. I tried to keep this program simple, but yes by using better algorithm you can always impress interviewer :)

Anonymous said...

int count = 0;
for(int i = 1; i < n; i++)
{
if(n % i == 0)
{
count = count + 1;
}
}
//System.out.print(count);
if(count > 1) {

can anyone explain the logic

Brian Stewart said...

If you want to store all primes below some N (as asked in the 30 programming questions page that brought me here), you only need to check whether a given number is divisible by the primes already found.

e.g.

You find 2, 3, 5.

To check 7 you only need to see if it's divisible by those.
This works since if a number n is divisible by k, k is either prime or has a prime factor (say j) and thus only primes need to be tested. Sample code, which can be further sped up, written while I'm elbow deep in tomatoes and pasta but seemed to work.

std::vector getVectorOfPrimes(int N) {
std::vector primes;
if (N <= 1) {
// No primes below 2!
} else {
primes.push_back(2);
int numPrimesFound = 1;
for (int i = 3; i <= N; i += 2) {
bool isPrime = true;
for (int j = 0; j < numPrimesFound; ++j) {
if (i % primes[j] == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.push_back(i);
++numPrimesFound;
}
}
}

return primes;
}

Yogesh..BG said...

the check can be between sqrt(n) or n/2.

Jonathan said...

Hey wait a minute the example just goes from 20. What about 21. It is not a prime number. The comment of 1-100 is false. This program just prints odd numbers. This code is broken. The sqrt of n is a better solution as others has suggested is better.

Anonymous said...

that code is fine with in 1000 but it worst case when we enter 10000000

anuroop desu said...

You can get the prime number program in java at
http://letusprogram.wordpress.com/2013/07/17/prime-number-program-in-java/

Muhammad Umair Baig said...

// best way to check prime number
boolean isPrime(int number) {
if (number%2 == 0) return false;
for(int i=3;i*i<=number;i+=2){
if (number%i == 0) return false;
}
return true;
}
http://csharplanguageontips.blogspot.com/

Anonymous said...

I copy/pasted this code in my java code input window (jGrasp) but it came back with two errors.....

"Scanner.java:1: error: Scanner is already defined in this compilation unit
import java.util.Scanner;
^
Scanner.java:14: error: constructor Scanner in class Scanner cannot be applied to given types;
int limit = new Scanner(System.in).nextInt();
^
required: no arguments
found: InputStream
reason: actual and formal argument lists differ in length
2 errors"

What happened?

Anonymous said...

How can I return the first number bigger than a get number n? Please help me.

Anonymous said...

public static String isPrime(int num)
{
if(num<0)
return "not valid";
if(num==0||num==1)
return "not prime";
if(num==2||num==3)
return "prime number";
if((num*num-1)%24==0)
return "prime";
else return "not prime";
}

easy way to check for prime numbers...

hemo the magnificent said...

@Anonymous
That algorithm will give you too many positives. The test:
(num*num - 1)%24 == 0
is true for all prime num, but it's also true for some non-primes (starting with 25).

Anonymous said...

TRY THESE AS A WHOLE IT MIGHT HELP

if(a%2!=0 && a%3!=0 && a%5!=0 && a%7!=0){System.out.println(a+" is a prime number");}
else{System.out.println(a+" is not a prime number");}

if(a%2==0) {System.out.println(a+ " The number is even");}
else{System.out.println(a+ " Is not even");}

if(a%2==1) {System.out.println(a+ " Is odd");}
else{System.out.println(a+ " Is not odd") ;}

None said...

Ok what's wrong with this:

public static boolean isPrime( int number ) {
if(number % 2 == 0)
return false;
else if(number % 3 == 0)
return false;
else
return true;
}

None said...

Sorry made a mistake and posted the wrong code. This is the correct code:

public static boolean isPrime( int number ) {
if( (number % 2) == 0 || (number % 3) == 0 || number == 1 )
return false;
return true;
}

smily suma said...

can u please provide basic core java programs for expeienced interview people

Anonymous said...

public boolean isPrime(int n){ //Header according to Question reqirement
boolean isPrime=true;
int divider=2;

while(divider<n){
if(n%divider==0)
isPrime=false;
divider++;
}
return isPrime;
}

Anonymous said...

Using Sieve of Eratosthenes logic avoids most of the problems here, though it does take more than just a couple of lines to code. It is also 'limited' in the sense that you can only go so far before you will reach limits imposed by your hardware or programming language.

Post a Comment