Program to print prime numbers from 1 to N.

Given a number N, the task is to print the prime numbers from 1 to N.
Examples: 

Input: N = 10
Output: 2, 3, 5, 7
Input: N = 5
Output: 2, 3, 5 

Algorithm to print prime numbers:  

• First, take the number N as input.
• Then use a for loop to iterate the numbers from 1 to N
• Then check for each number to be a prime number. If it is a prime number, print it.

Approach 1: Print prime numbers using loop.

Now, according to formal definition, a number ‘n’ is prime if it is not divisible by any number other than 1 and n. In other words a number is prime if it is not divisible by any number from 2 to n-1. so, we have to run a loop from 2 to n-1 and If a number is divisible by any number from 2 to n-1 it is not a prime number.

Below is the implementation of the above approach:  

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 

Time Complexity: O(N^2), 
Auxiliary Space: O(1)

Approach 2: Optimize the first approach

For checking if a number is prime or not do we really need to iterate through all the number from 2 to n-1? We already know that a number ‘n’ cannot be divided by any number greater than ‘n/2’. So, according to this logic we only need to iterate through 2 to n/2 since number greater than n/2 cannot divide n.

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 

Time Complexity: O(N²), 
Auxiliary Space: O(1), since no extra space has been taken.

Approach 3:

If a number ‘n’ is not divided by any number less than or equals to the square root of n then, it will not be divided by any other number greater than the square root of n. So, we only need to check up to the square root of n.

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 

Time Complexity: O(N^(3/2)),
Auxiliary Space: O(1)

Approach 4: Sieve of Eratosthenes Algorithm

1. Create a boolean array is_prime of size (N+1), initialized with true values for all elements.
2. Loop through the array is_prime from 2 to the square root of N (inclusive), and for each prime number p found in the loop:
   • If is_prime[p] is true, loop through the multiples of p from p*p up to N, and mark them as false in the is_prime array.
3. Loop through the array is_prime from 2 to N (inclusive), and for each index i where is_prime[i] is true, print i as a prime number.

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 

Complexity Analysis:

Time complexity:

• The outer loop runs from 2 to the square root of N, so it runs in O(sqrt(N)) time.
• The inner loop runs from p*p to N, and for each prime number p, it eliminates the multiples of p up to N. Therefore, the inner loop runs at most N/p times for each prime number p, so it has a time complexity of O(N/2 + N/3 + N/5 + …), which is approximately O(N log(log(N))). This is because the sum of the reciprocals of the prime numbers up to N is asymptotically bounded by log(log(N)).
• The final loop runs from 2 to N, so it has a time complexity of O(N).
• Therefore, the overall time complexity of the algorithm is O(N log(log(N))).

Space complexity:

• The algorithm uses an array of size N+1 to store the boolean values of whether each number is prime or not. Therefore, the space complexity is O(N).

In summary, the Sieve of Eratosthenes algorithm has a time complexity of O(N log(log(N))) and a space complexity of O(N) to print all the prime numbers from 1 to N.

To know more check  Sieve of Eratosthenes.

Optimized Sieve of Eratosthenes Method: (Bitwise Sieve Method)

One optimization of the Sieve of Eratosthenes method is, we have skipped all even numbers altogether. We reduce the size of the prime array to half. We also reduce all iterations to half.

Steps:

1. Create a boolean array prime of size (n/2), initialized with false values for all elements.
2. As except 2, there are not any even prime numbers, so we skip 2 and then check for only odd numbers, so that we just have to check half elements.
3. Inside the loop:
   1. In each iteration, if prime[i/2] is false, then loop through the multiples of i from i*i up to N with increment of 2*i, and mark them as true in the prime array.
4. Finally, first print 2 and then loop through the array prime from 3 to N (inclusive), and for each index i/2 where prime[i/2] is false, print i as a prime number.

Below is the implementation:

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 

Time Complexity: O(n*log(log n)), where n is the difference between the intervals.
Space Complexity: O(n)