C++ 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:
- 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: Now, according to the 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.
Below is the implementation of the above approach:
C++
// C++ program to display // Prime numbers till N #include <bits/stdc++.h> using namespace std; // Function to check if a // given number is prime bool isPrime( int n) { // Since 0 and 1 is not // prime return false. if (n == 1 || n == 0) return false ; // Run a loop from 2 to n-1 for ( int i = 2; i < n; i++) { // if the number is divisible by i, // then n is not a prime number. if (n % i == 0) return false ; } // Otherwise n is a prime number. return true ; } // Driver code int main() { int N = 100; // Check for every number from 1 to N for ( int i = 1; i <= N; i++) { // Check if current number is prime if (isPrime(i)) { cout << i << " " ; } } return 0; } |
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), Space Complexity: O(1)
Approach 2: 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.
C++
// C++ program to display // Prime numbers till N #include <bits/stdc++.h> using namespace std; // Function to check if a given // number is prime bool isPrime( int n) { // Since 0 and 1 is not prime // return false. if (n == 1 || n == 0) return false ; // Run a loop from 2 to n/2. for ( int i = 2; i <= n / 2; i++) { // If the number is divisible by i, // then n is not a prime number. if (n % i == 0) return false ; } // Otherwise n is a prime number. return true ; } // Driver code int main() { int N = 100; // Check for every number from 1 to N for ( int i = 1; i <= N; i++) { // Check if current number is prime if (isPrime(i)) { cout << i << " " ; } } return 0; } |
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), Space Complexity: O(1)
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.
C++
// C++ program to display // Prime numbers till N #include <bits/stdc++.h> using namespace std; // Function to check if a given // number is prime bool isPrime( int n) { // Since 0 and 1 is not prime // return false. if (n == 1 || n == 0) return false ; // Run a loop from 2 to // square root of n. for ( int i = 2; i * i <= n; i++) { // If the number is divisible by i, // then n is not a prime number. if (n % i == 0) return false ; } // Otherwise n is a prime number. return true ; } // Driver code int main() { int N = 100; // Check for every number from 1 to N for ( int i = 1; i <= N; i++) { // Check if current number is prime if (isPrime(i)) { cout << i << " " ; } } return 0; } |
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)), Space Complexity: O(1)
You can further optimize the time complexity to O(n*log(log(n))).
Approach 4: Sieve of Eratosthenes Algorithm
Create a boolean array is_prime of size (N+1), initialized with true values for all elements.
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.
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.
C++
// CPP program to print prime numbers from 1 to N // using Sieve of Eratosthenes #include <bits/stdc++.h> using namespace std; void sieve_of_eratosthenes( int n) { bool is_prime[n + 1]; memset (is_prime, true , sizeof (is_prime)); is_prime[0] = is_prime[1] = false ; for ( int p = 2; p * p <= n; p++) { if (is_prime[p]) { for ( int i = p * p; i <= n; i += p) { is_prime[i] = false ; } } } for ( int i = 2; i <= n; i++) { if (is_prime[i]) { cout << i << " " ; } } } int main() { sieve_of_eratosthenes(100); return 0; } // This code is contributed by Susobhan Akhuli |
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.
Please refer complete article on Program to print prime numbers from 1 to N. for more details!
Contact Us