Print prime numbers from 1 to N in reverse order

0 0 5 minutes read

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 2

Input : 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 Program
int 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
// Eratosthenes
import 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 Eratosthenes
def 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 input
N = 25;
 
# to display
print("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
// Eratosthenes
using 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 Eratosthenes
 
function 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 display
echo "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
// Eratosthenes
 
 
function 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 input
let N = 25;
 
// to display
document.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 zambiatek!