Table of contents
1.
Introduction
2.
Algorithm
3.
Examples 
3.1.
Example 1
3.2.
Example 2
3.3.
Example 3
4.
Time and Space Complexity
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
Can we optimize the prime number generation further?
5.2.
Why do we check divisibility only up to the square root of a number?
5.3.
Can we use these algorithms to check the primality of a single number?
6.
Conclusion
Last Updated: Nov 13, 2024
Easy

Print Prime Numbers from 1 to N in Java

Author Ravi Khorwal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A prime number is a positive integer greater than 1 with no positive integer divisors other than 1 & itself. In other words, it can only be divided evenly by 1 & itself. Examples of prime numbers include 2, 3, 5, 7, 11, 13, 17, 19, and so on. These unique numbers play a fundamental role in many fields of mathematics and computer science, especially in computer algorithms, which consist of cryptography and number theory. 

Print Prime Numbers from 1 to N in Java

In this article, we will learn how to print prime numbers from 1 to a given number (N) using Java. We will discuss different approaches, such as using a for loop, a while loop, and creating a separate method. At the end, we will discuss the time and space complexity of the algorithms used.

Algorithm

To print prime numbers from 1 to N, we can follow these steps:

1. Start a loop from 2 to N (since 1 is not a prime number).
 

2. For each number i in the loop, check if it is prime by doing the following:
 

   a. Start another loop from 2 to the square root of i.
 

   b. If i is divisible by any number in this loop, it is not prime. Break the loop.
 

   c. If the inner loop completes without finding any divisors, i is prime. Print it.
 

3. Continue the outer loop until all numbers from 2 to N have been checked.
 

The pseudocode for the algorithm is:

function printPrimes(N):
    for i = 2 to N:
        isPrime = true
        for j = 2 to sqrt(i):
            if i % j == 0:
                isPrime = false
                break
        if isPrime:
            print i


This algorithm checks each number from 2 to N for primality by trying to divide it by numbers from 2 to its square root. If any divisor is found, the number is not prime. If no divisors are found, the number is prime & is printed.

Examples 

Now, let’s discuss a few different programs to understand how to print prime numbers from 1 to N in Java.

Example 1

Java Program to Print Prime Numbers from 1 to N using For Loop:

public class PrimeNumbersForLoop {
    public static void main(String[] args) {
        int N = 20;
        System.out.println("Prime numbers from 1 to " + N + ":");
        
        for (int i = 2; i <= N; i++) {
            boolean isPrime = true;
            
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            if (isPrime) {
                System.out.print(i + " ");
            }
        }
    }
}
You can also try this code with Online Java Compiler
Run Code


Output:

Prime numbers from 1 to 20:
2 3 5 7 11 13 17 19
You can also try this code with Online Java Compiler
Run Code


In this code : 

1. We start by defining the value of N, which represents the upper limit of the range of numbers we want to check for primality.
 

2. We use a for loop to iterate from 2 to N (inclusive).
 

3. For each number i, we initialize a boolean variable isPrime to true, assuming the number is prime initially.
 

4. We start another for loop from 2 to the square root of i.
 

   - If i is divisible by any number j in this range, we set isPrime to false & break the inner loop.
 

5. After the inner loop ends, we check the value of isPrime.
 

   - If isPrime is still true, it means i is prime, so we print it.
 

6. The outer loop continues until all numbers from 2 to N have been checked.


This program efficiently checks each number for primality by using the square root optimization. Instead of checking divisibility up to i-1, we only need to check up to the square root of i, as any factor greater than the square root would have a corresponding factor less than the square root.

Example 2

Java Program to Print Prime Numbers from 1 to 100 using While Loop:

public class PrimeNumbersWhileLoop {
    public static void main(String[] args) {
        int N = 100;
        int i = 2;
        
        System.out.println("Prime numbers from 1 to " + N + ":");
        
        while (i <= N) {
            boolean isPrime = true;
            int j = 2;
            
            while (j <= Math.sqrt(i)) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
                j++;
            }
            
            if (isPrime) {
                System.out.print(i + " ");
            }
            
            i++;
        }
    }
}
You can also try this code with Online Java Compiler
Run Code


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

 

In this code: 

1. We start by defining the value of N as 100, which represents the upper limit of the range of numbers we want to check for primality.
 

2. We initialize a variable i to 2, which will be used to iterate through the numbers.
 

3. We use a while loop to iterate from 2 to N (inclusive).
 

4. For each number i, we initialize a boolean variable isPrime to true, assuming the number is prime initially.
 

5. We start another while loop with a variable j initialized to 2.
 

   - We check if i is divisible by j. If it is, we set isPrime to false & break the inner loop.
 

   - If i is not divisible by j, we increment j & continue the loop until j becomes greater than the square root of i.
 

6. After the inner loop ends, we check the value of isPrime.
 

   - If isPrime is still true, it means i is prime, so we print it.
 

7. We increment i & continue the outer loop until i becomes greater than N.
 

This program uses a while loop to iterate through the numbers and check for primality. The logic for checking primality is similar to the previous example using a for loop.

Example 3

Java Program to display Prime Numbers from 1 to N using Method:

In this example, we will create a separate method to check if a number is prime & use it to print prime numbers from 1 to N.

public class PrimeNumbersMethod {
    public static void main(String[] args) {
        int N = 50;
        System.out.println("Prime numbers from 1 to " + N + ":");
        
        for (int i = 2; i <= N; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
    }
    
    public static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}
You can also try this code with Online Java Compiler
Run Code


Output:

Prime numbers from 1 to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47


In this code: 

1. We define a method called `isPrime` that takes an integer `num` as input & returns a boolean value indicating whether `num` is prime or not.

2. Inside the `isPrime` method:

   - We first check if `num` is less than 2. If it is, we return `false` since numbers less than 2 are not considered prime.
 

   - We use a for loop to iterate from 2 to the square root of `num`.
 

     - If `num` is divisible by any number `i` in this range, we return `false` since `num` is not prime.
 

   - If the loop completes without finding any divisors, we return `true` since `num` is prime.

3. In the `main` method:

   - We define the value of `N` as 50, representing the upper limit of the range of numbers we want to check for primality.
 

   - We use a for loop to iterate from 2 to `N` (inclusive).
 

   - For each number `i`, we call the `isPrime` method to check if it is prime.
 

     - If `isPrime` returns `true`, we print the number.
 

By creating a separate `isPrime` method, we can reuse the logic for checking primality in other parts of the program or in other programs as well. This promotes code reusability and modularity.

Time and Space Complexity

Time Complexity

- In all the above examples (using for loop, while loop, and method), we iterate from 2 to N to check each number for primality.

- For each number, we perform a nested loop from 2 to the square root of the number to check for divisibility.

- The outer loop runs N-1 times, and the inner loop runs sqrt(N) times in the worst case.

- Therefore, the time complexity of these algorithms is O(N * sqrt(N)).

Space Complexity

- In the examples using for loop and while loop, we only use a constant amount of extra space for variables like `isPrime`, `i`, and `j`.

- In the example using a method, we use a constant amount of extra space for the `isPrime` method call stack.

- Therefore, the space complexity of these algorithms is O(1), which means they use constant extra space regardless of the input size.


It's important to remember that while the time complexity of O(N * sqrt(N)) is better than the brute force approach of checking each number up to N-1, there are more optimized algorithms for generating prime numbers, like the Sieve of Eratosthenes, which has a time complexity of O(N * log(log(N))).

Frequently Asked Questions

Can we optimize the prime number generation further?

Yes, algorithms like the Sieve of Eratosthenes can generate prime numbers more efficiently, with a time complexity of O(N * log(log(N))).

Why do we check divisibility only up to the square root of a number?

If a number is not prime, it must have a factor less than or equal to its square root. Checking beyond the square root is redundant.

Can we use these algorithms to check the primality of a single number?

Yes, we can modify the code to check the primality of a single number by removing the outer loop and directly checking the given number.

Conclusion

In this article, we discussed different methods to print prime numbers from 1 to N using Java. We implemented programs using a for loop, a while loop, and a separate method. We also analyzed the time and space complexity of the algorithms. With the help of these concepts and techniques, you can efficiently generate prime numbers and apply them in different programming situations. Remember, there are more advanced algorithms available for generating prime numbers with better time complexity.

You can also check out our other blogs on Code360.

Live masterclass