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.