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 a prime number if it's 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 numbers which is relatively easier than Java exercises. This Simple Java program prints prime numbers starting from 1 to 100 or any specified number. It also has a method that 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 the 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 a 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 the 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 numbers from 1 to 20
2
3
5
7
11
13
17
19
/**
* 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 numbers from 1 to 20
2
3
5
7
11
13
17
19
In this Java program, we have two-part, the first part which is taking input from the user to print prime numbers, and the 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 of its encapsulated logic of checking prime numbers. There is also another popular Java question is "How to check if a number is prime or not?", isPrime() can be used there. it's 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 it's divisible by another number means it's not prime.
That's all on how to print prime numbers in Java or how to check if a number is prime or not. It's 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, which will give you thinking time on how this Java program is working and checking for prime numbers.
Related Java Program tutorials
And now is the quiz time, What is the time complexity of this algorithm to print prime numbers in Java? can you improve this by using any data structure or different approach?
Also what is your favorite coding exercise? Palindrom, Prime number or Reverse a given String in Java?
There are many better ways of improving its complexity. This code has the worse case complexity
ReplyDelete@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.
ReplyDeleteYou 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).
ReplyDeleteIn 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.
ReplyDeleteNo 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.
@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.
ReplyDeleteOne good example of prime numbers in Java is hashcode(). hashcode() uses prime number as multiplier in order to generate uniform and unique hashcode.
ReplyDeletefew more question
ReplyDeletehow 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.
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.
ReplyDeleteonly better thing than java program is C++ program... :o)
ReplyDeleteobviously in both cases I mean "well written" program... ;o)
There are many better ways of improving its complexity. This code has the worse case complexity
ReplyDeleteAlso you dont need to check each number. If you can not devide by 2 you can skeep even numbers:
ReplyDeleteif (a % 2 == 0)
return false;
for (int i = 3; i < Math.sqrt(n); i+=2)
if (a % i == 0)
return false;
return true;
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.
ReplyDelete@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 :)
ReplyDeleteint count = 0;
ReplyDeletefor(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
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.
ReplyDeletee.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;
}
the check can be between sqrt(n) or n/2.
ReplyDeleteHey 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.
ReplyDeletethat code is fine with in 1000 but it worst case when we enter 10000000
ReplyDeleteYou can get the prime number program in java at
ReplyDeletehttp://letusprogram.wordpress.com/2013/07/17/prime-number-program-in-java/
// best way to check prime number
ReplyDeleteboolean 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/
I copy/pasted this code in my java code input window (jGrasp) but it came back with two errors.....
ReplyDelete"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?
How can I return the first number bigger than a get number n? Please help me.
ReplyDeletepublic static String isPrime(int num)
ReplyDelete{
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...
@Anonymous
ReplyDeleteThat 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).
TRY THESE AS A WHOLE IT MIGHT HELP
ReplyDeleteif(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") ;}
Ok what's wrong with this:
ReplyDeletepublic static boolean isPrime( int number ) {
if(number % 2 == 0)
return false;
else if(number % 3 == 0)
return false;
else
return true;
}
Sorry made a mistake and posted the wrong code. This is the correct code:
ReplyDeletepublic static boolean isPrime( int number ) {
if( (number % 2) == 0 || (number % 3) == 0 || number == 1 )
return false;
return true;
}
can u please provide basic core java programs for expeienced interview people
ReplyDeletepublic boolean isPrime(int n){ //Header according to Question reqirement
ReplyDeleteboolean isPrime=true;
int divider=2;
while(divider<n){
if(n%divider==0)
isPrime=false;
divider++;
}
return isPrime;
}
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.
ReplyDeletePlz check it , it will take n^(1/2) to execute!!
ReplyDeleteboolean isPrime(int num) {
int temp = Math.sqrt(num);
for(int i = 2; i<=temp;i++) {
if(num%i==0) {
return true;
break;
}
}
return false;
}
This works fine
ReplyDeleteprivate boolean isPrime(int n)
{
if (n <= 1 || n%2 == 0) {
return false;
}
for (int i = 3; i <=(n/2); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
public class prime {
ReplyDeletestatic void primemethod(int n)
{
boolean status=false;
for(int i=2;i<n;i++)
{
int res=n%i;
if(res==0)
{
System.out.println("not a prime num...");
status=true;
break;
}
}
if(status==false)
{
System.out.println("prime number....");
}
}
public static void main(String args[])
{
prime.primemethod(11);
}
}
Check this out
print hundread prime number as--->
ReplyDeleteclass Prime{
public static void main(String args[]){
int count=0;
for(int i=2;;i++){
boolean flag=false;
for(int j=2;j<i;j++){
if(i%j==0){
flag=true;;
break;
}
}
if(flag==false){
System.out.println((count+1)+"== "+i);
count++;
}
if(count==100){
break;
}
}
}
}
If you're evaluating your own prime verifying code, or the code of an interviewee, one detail to pay careful attention to is the number "2".. All even numbers > 2 are not prime, but 2 itself is.
ReplyDeleteI want prime numbers which are separated by 2 like{3,5}{5,7}{11,13}.........{881,883}.
ReplyDeletei want this upto 1000.
public static boolean isPrime(int number){
ReplyDeletefor(int i=2; number/i>i; i++){
if(number%i == 0){
return false;
}
}
return true;
}
This can be the programm with least complxity.I am using here number properties
/**
ReplyDelete*
*/
package com.practice.prime;
/**
* @author gramaswai
*
*/
public class PrimeNumberVerifier {
public boolean isPrimeNo(int no) {
boolean reminderNotZero = true;
int i = 1;
while(reminderNotZero) {
++i;
reminderNotZero = isReminderNotZero(i , no);
}
System.out.println("No "+no+" Divided by "+i);
return no == i;
}
private boolean isReminderNotZero(int i, int no) {
int j = no % i;
return j!=0;
}
}
plzz tell me correct programing for using boolean data type for print prime number
ReplyDelete