Given a number N, print all prime number smaller than or equal to N in reverse order .
For example, if N is 9, the output should be “7, 5, 3, 2”.
Examples:
Input : N = 5
Output : 5 3 2Input : N = 20
Output : 19 17 13 11 7 5 3 2
A simple solution is to traverse from N to 1. For every number, check if it is a prime using school method to check for prime. Print the number if it is prime.
An efficient solution is to use Sieve of Eratosthenes. We efficiently find all number from 1 to N, then print them.
C++
// C++ program to print all primes between 1// to N in reverse order using Sieve of// Eratosthenes#include <bits/stdc++.h>using namespace std;void Reverseorder(int n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i // is Not a prime, else true. bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Print all prime numbers in reverse order for (int p = n; p >= 2; p--) if (prime[p]) cout << p << " ";}// Driver Programint main(){ // static input int N = 25; // to display cout << "Prime number in reverse order" << endl; if (N == 1) cout << "No prime no exist in this range"; else Reverseorder(N); // calling the function return 0;} |
Java
// Java program to print all primes between 1// to N in reverse order using Sieve of// Eratosthenesimport java.io.*;import java.util.*;class GFG { static void reverseorder(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i // is Not a prime, else true. boolean prime[] = new boolean[n + 1]; for (int i = 0; i < n; i++) prime[i] = true; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int i = n; i >= 2; i--) if (prime[i] == true) System.out.print(i + " "); } // Driver Program to test above function public static void main(String args[]) { // static input int N = 25; // To display System.out.println("Prime number in reverse order"); if (N == 1) System.out.println("No prime no exist in this range"); else reverseorder(N); // calling the function }} |
Python3
# Python3 program to print all primes # between 1 to N in reverse order # using Sieve of Eratosthenesdef Reverseorder(n): # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [True] * (n + 1); p = 2; while(p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range((p * 2), (n + 1), p): prime[i] = False; p += 1; # Print all prime numbers in # reverse order for p in range(n, 1, -1): if (prime[p]): print(p, end = " ");# Driver Code# static inputN = 25;# to displayprint("Prime number in reverse order");if (N == 1): print("No prime no exist in this range");else: Reverseorder(N); # calling the function# This code is contributed by mits |
C#
// C# program to print all primes between 1// to N in reverse order using Sieve of// Eratosthenesusing System;class GFG { static void reverseorder(int n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as // true. A value in prime[i] will // finally be false if i is Not a // prime, else true. bool []prime = new bool[n + 1]; for (int i = 0; i < n; i++) prime[i] = true; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int i = n; i >= 2; i--) if (prime[i] == true) Console.Write(i + " "); } // Driver code public static void Main() { // static input int N = 25; // To display Console.WriteLine("Prime number in" + " reverse order"); if (N == 1) Console.WriteLine("No prime no" + " exist in this range"); else // calling the function reverseorder(N); }}// This code is contributed by Sam007. |
PHP
<?php// PHP program to print all primes // between 1 to N in reverse order // using Sieve of Eratosthenesfunction Reverseorder($n){ // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. $prime = array_fill(0, $n + 1, true); for ($p = 2; $p * $p <= $n; $p++) { // If prime[p] is not changed, // then it is a prime if ($prime[$p] == true) { // Update all multiples of p for ($i = $p * 2; $i <= $n; $i += $p) $prime[$i] = false; } } // Print all prime numbers in // reverse order for ($p = $n; $p >= 2; $p--) if ($prime[$p]) echo $p." ";}// Driver Code// static input$N = 25;// to displayecho "Prime number in reverse order\n";if ($N == 1) echo "No prime no exist in this range";else Reverseorder($N); // calling the function// This code is contributed by mits?> |
Javascript
<script>// Javascript program to print all primes between 1// to N in reverse order using Sieve of// Eratosthenesfunction Reverseorder( n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i // is Not a prime, else true. let prime = new Array(n + 1); for (let i = 0; i < n; i++) prime[i] = true; for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) prime[i] = false; } } // Print all prime numbers in reverse order for (let p = n; p >= 2; p--) if (prime[p]) document.write(p + " ");}// Driver Code// static inputlet N = 25;// to displaydocument.write("Prime number in reverse order" + "</br>");if (N == 1) document.write("No prime no exist in this range");else Reverseorder(N); // calling the function</script> |
Output:
Prime number in reverse order 23 19 17 13 11 7 5 3 2
Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(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!
… [Trackback]
[…] Read More Information here to that Topic: geeksforgeeks.org/print-prime-numbers-from-1-to-n-in-reverse-order/ […]