In this article, I'll share you a simple problem about writing a Java program to print prime numbers up to a given number e.g. say prime numbers from 1 to 100. It's one of the most common coding exercises for programmers learning in Java, as it gives you an opportunity to learn more about essential operator in Java Programming. The key here is that you cannot use a library function which can simply your job, you need to devise the algorithm for checking prime number by yourself. One of the most popular algorithms for generating prime is Sieve of Eratosthenes, which we have discussed earlier, but in this post, we will take a simpler approach. We'll first write a function to check whether a number is prime or not and then we loop through first 100 numbers i.e. from 1 to 100 and print only those which passed the prime test. Btw, if you are looking for some serious programming coding question for the interview, then you can also take a look at Cracking the coding interview, which contains more than 150 coding question with solutions.

##

A number is said to be prime if it's not divisible by any number other than itself e.g. 2, 3 or 5. 1 is not counted as a prime number, so the lowest prime number is 2. One of the easiest way to check whether a number is prime or not is to loop from 2 to the number itself and checks if it's divisible by any number in between or not.

You can do that check by using modulus operator in Java, which return zero if a number is perfectly divisible by another number. If the number you are checking is not divisible by anyone then it's a prime number otherwise, it's not a prime number.

But this logic can be further optimized to only loop through the square root of the number instead of the number itself, as shown in below example. This will make the Java program fast for checking large prime numbers.

Here is a list of all prime numbers between 1 and 100:

That's all about

Here are couple of more coding problems for practice:

The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

##
__How to check if a number is prime or not__

A number is said to be prime if it's not divisible by any number other than itself e.g. 2, 3 or 5. 1 is not counted as a prime number, so the lowest prime number is 2. One of the easiest way to check whether a number is prime or not is to loop from 2 to the number itself and checks if it's divisible by any number in between or not.You can do that check by using modulus operator in Java, which return zero if a number is perfectly divisible by another number. If the number you are checking is not divisible by anyone then it's a prime number otherwise, it's not a prime number.

But this logic can be further optimized to only loop through the square root of the number instead of the number itself, as shown in below example. This will make the Java program fast for checking large prime numbers.

Here is a list of all prime numbers between 1 and 100:

__An optimized way to generate Prime numbers from 1 to 100__/** * Java Program to print prime numbers from 1 to 100 * * @author Javin Paul */ public class PrimeNumberGenerator { public static void main(String args[]) { // print prime numbers from 1 - 100 System.out.println("Prime numbers from 1 to 100 "); for (int i = 2; i <= 100; i++) { if (isPrime(i)) { System.out.println(i); } } } /* * An optimized to check if a number is prime or not. */ public static boolean isPrime(int num) { if (num == 2 || num == 3) { return true; } if (num % 2 == 0 || num % 3 == 0) { return false; } for (int i = 3; i < Math.sqrt(num); i += 2) { if (num % i == 0 || num % Math.sqrt(num) == 0) { return false; } } return true; } } Output: Prime numbers from 1 to 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

That's all about

**how to print prime numbers in Java from 1 to 100**. Let me know if you find any bug on this program or you think if this program will not work in any specific scenario. This looks much more optimized than looping till the number itself.Here are couple of more coding problems for practice:

- Top 10 Programming problems from Java Interviews? (article)
- Write code to implement Quicksort algorithm in Java? (algorithm)
- How do you swap two integers without using a temporary variable? (solution)
- Write a program to check if a number is a power of two or not? (solution)
- How to reverse String in Java without using StringBuffer? (solution)
- Write a program to code insertion sort algorithm in Java (program)
- How to find a missing number in a sorted array? (solution)
- How to calculate factorial using recursion and iteration? (solution)
- How do you reverse word of a sentence in Java? (solution)
- How to find duplicate characters from String in Java? (solution)
- How to reverse an int variable in Java? (solution)
- How to check if a year is a leap year in Java? (answer)
- Write code to implement Bubble sort algorithm in Java? (code)
- How to print Pyramid pattern in Java? (solution)
- How to check if a given number is prime or not? (solution)
- How to solve FizzBuzz problem in Java? (solution)
- Write a program to print the highest frequency word from a text file? (solution)
- How to remove duplicate elements from ArrayList in Java? (solution)
- How to find if given String is a palindrome in Java? (solution)

__Further Reading__Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

the new blog looks really good. Thanks.

ReplyDeleteAnother interesting read. But there is a bug in the code. When testing n for prime, the logic should check reminder from 3 up to (and including) square root of n. That is why 25 and 49 are showing up as "prime" in your output.

ReplyDeleteif (num % i == 0 || num % Math.sqrt(num) == 0)

ReplyDelete@Clarence and @Marverick, Good catch, thanks

ReplyDelete'isPrimeOrNot' is a terrible name for a function... 'isPrime' describes way better what the function does. Also, you must have some other bug lying around because your result also contains 9 which is not prime...

ReplyDelete@Leandro, agree, changed to isPrime(), make more sense. Regarding 9, you are correct, 9 is not a prime number, corrected the logic.

DeleteYou've written that 2 is a prime number then why there is no 2 in output result?

ReplyDelete@Alekesy, Good spotting, corrected it now. Thanks

DeleteNeat code. I would like to suggest an improvement

ReplyDeleteAt this piece of code

for (int i = 3; i < Math.sqrt(num); i += 2)

{

if (num % i == 0 || num % Math.sqrt(num) == 0) {

return false;

}

With a slight change the or (||) statement could be omitted. The counter 'i' could be also checked for equality to the square root of num. Hence i <= Math.sqrt(num).

@Anonymous, good suggestion, thanks

DeleteShouldn't we cache Math.sqrt value?

ReplyDelete@Anonymous, calculating square is not as costly as calculating factorial or fibonacci numbers, but yes, for improved performance you can surely cache.

Deletesuperb blog for java study..

ReplyDeleteThank you @Somesh, please share your friends, it does help a lot.

Deletenice

ReplyDeleteThanks @Anna, glad that you like this post about generating prime numbers in Java. If you want to learn about different methods then don't forget to check the Sieve of Eratosthenes algorithm for generating prime numbers as well.

DeleteHi Javin. Firstly, thanks for your good articles. I'm your new subscriber.

ReplyDeleteI wondered why didn't use num%Math.sqrt(num) in first if condition. Because num not changes. If we use like this, it can reduce complexity of algorithm and in some situation maybe increase efficiency. Again thank you so much. Good work.

if (num % 2 == 0 || num % 3 == 0 || Math.sqrt(num)) {

return false;

}

for (int i = 3; i < Math.sqrt(num); i += 2) {

if (num % i == 0) {

return false;

}

}

I really like your blog, but I can't tell you how frustrating it is not being able to simply copy and paste the examples into eclipse and simply run them ... do you do that on purpose? just curious

ReplyDeletebut why it doesnt show the ms that takes to print

ReplyDelete