Given a number N, the task is to print all prime numbers less than or equal to N.
Examples:
Input: 7 Output: 2, 3, 5, 7 Input: 13 Output: 2, 3, 5, 7, 11, 13
Naive Approach: Iterate from 2 to N, and check for prime. If it is a prime number, print the number.
Below is the implementation of the above approach:
C++
// C++ program to print all primes less than N #include <bits/stdc++.h> using namespace std; // function check whether a number is prime or not bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function to print primes void printPrime(int n) { for (int i = 2; i <= n; i++) if (isPrime(i)) cout << i << " "; } // Driver Code int main() { int n = 7; printPrime(n); } |
C
// C program to print all primes less than N #include <stdbool.h> #include <stdio.h> // function check whether a number is prime or not bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function to print primes void printPrime(int n) { for (int i = 2; i <= n; i++) if (isPrime(i)) printf("%d ", i); } // Driver Code int main() { int n = 7; printPrime(n); } // This code is contributed by Sania Kumari Gupta |
Java
// Java program to print // all primes less than N class GFG { // function check whether // a number is prime or not static boolean isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function to print primes static void printPrime(int n) { for (int i = 2; i <= n; i++) { if (isPrime(i)) System.out.print(i + " "); } } // Driver Code public static void main(String[] args) { int n = 7; printPrime(n); } } // This code is contributed // by ChitraNayal |
Python3
# Python3 program to print # all primes less than N # Function to check whether # a number is prime or not . def isPrime(n): # Corner case if n <= 1 : return False # check from 2 to n-1 for i in range(2, n): if n % i == 0: return False return True # Function to print primes def printPrime(n): for i in range(2, n + 1): if isPrime(i): print(i, end = " ") # Driver code if __name__ == "__main__" : n = 7 # function calling printPrime(n) # This code is contributed # by Ankit Rai |
C#
// C# program to print // all primes less than N using System; class GFG { // function check whether // a number is prime or not static bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function to print primes static void printPrime(int n) { for (int i = 2; i <= n; i++) { if (isPrime(i)) Console.Write(i + " "); } } // Driver Code public static void Main() { int n = 7; printPrime(n); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP program to print // all primes less than N // function check whether // a number is prime or not function isPrime($n) { // Corner case if ($n <= 1) return false; // Check from 2 to n-1 for ($i = 2; $i < $n; $i++) if ($n % $i == 0) return false; return true; } // Function to print primes function printPrime($n) { for ($i = 2; $i <= $n; $i++) { if (isPrime($i)) echo $i . " "; } } // Driver Code $n = 7; printPrime($n); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to print all primes // less than N // function check whether a number // is prime or not function isPrime(n) { // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (let i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Function to print primes function printPrime(n) { for (let i = 2; i <= n; i++) { if (isPrime(i)) document.write(i +" "); } } // Driver Code let n = 7; printPrime(n); // This code is contributed by Mayank Tyagi </script> |
Output:
2 3 5 7
Time Complexity: O(N * N)
Auxiliary Space: O(1)
A better approach is based on the fact that one of the divisors must be smaller than or equal to ?n. So we check for divisibility only till ?n.
C++
// C++ program to print all primes // less than N #include <bits/stdc++.h> using namespace std; // function check whether a number // is prime or not bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to print primes void printPrime(int n) { for (int i = 2; i <= n; i++) { if (isPrime(i)) cout << i << " "; } } // Driver Code int main() { int n = 7; printPrime(n); } |
Java
// Java program to print // all primes less than N import java.io.*; class GFG { // function check // whether a number // is prime or not static boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so // that we can skip // middle five numbers // in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to print primes static void printPrime(int n) { for (int i = 2; i <= n; i++) { if (isPrime(i)) System.out.print(i + " "); } } // Driver Code public static void main (String[] args) { int n = 7; printPrime(n); } } // This code is contributed // by anuj_67. |
C#
// C# program to print // all primes less than N using System; class GFG { // function check // whether a number // is prime or not static bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so // that we can skip // middle five numbers // in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to print primes static void printPrime(int n) { for (int i = 2; i <= n; i++) { if (isPrime(i)) Console.Write(i + " "); } } // Driver Code public static void Main () { int n = 7; printPrime(n); } } // This code is contributed // by ChitraNayal |
Python3
# function to check if the number is # prime or not def isPrime(n) : # Corner cases if (n <= 1) : return False if (n <= 3) : return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0) : return False i = 5 while(i * i <= n) : if (n % i == 0 or n % (i + 2) == 0) : return False i = i + 6 return True # print all prime numbers # less than equal to N def printPrime(n): for i in range(2, n + 1): if isPrime(i): print (i, end =" ") n = 7 printPrime(n) |
Javascript
<script> // Javascript program to print all primes // less than N // function check whether a number // is prime or not function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to print primes function printPrime(n) { for (let i = 2; i <= n; i++) { if (isPrime(i)) document.write(i + " "); } } // Driver Code let n = 7; printPrime(n); // This code is contributed by subhammahato348. </script> |
PHP
<?php // PHP program to print // all primes less than N // function check whether // a number is prime or not function isPrime($n) { // Corner cases if ($n <= 1) return false; if ($n <= 3) return true; // This is checked so that // we can skip middle five // numbers in below loop if ($n % 2 == 0 || $n % 3 == 0) return false; for ($i = 5; $i * $i <= $n; $i = $i + 6) if ($n % $i == 0 || $n % ($i + 2) == 0) return false; return true; } // Function to print primes function printPrime($n) { for ($i = 2; $i <= $n; $i++) { if (isPrime($i)) echo $i . " "; } } // Driver Code $n = 7; printPrime($n); // This code is contributed // by ChitraNayal ?> |
Output:
2 3 5 7
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
The best solution is to use Sieve of Eratosthenes. The time complexity is O(N * loglog(N))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
