Super Prime

Last Updated : 29 Mar, 2025

Given a positive integer n and the task is to print all the Super-Primes less than or equal to n.

Super-prime numbers (also known as higher order primes) are the subsequence of prime number sequence that occupy prime-numbered positions within the sequence of all prime numbers. The first few super primes are 3, 5, 11, and 17.

Examples:

Input: n = 7
Output: 3 5
Explanation: In list of primes (2, 3, 5, 7}, 3 and 5 are super primes because they appear at 2nd and 3rd positions which are also a prime .

Input: n = 17
Output: 3 5 11 17
Explanation: In list of primes (2, 3, 5, 7, 11, 13, 17), 3, 5, 11 and 17 are super primes because they appear at 2nd, 3rd, 5th and 7th positions which are also a prime .

The idea is to generate all the primes less than or equal to the given number n using the Sieve of Eratosthenes. Once we have generated all such primes, we iterate through the array and print all prime number that occupy prime number positions.

C++

#include <bits/stdc++.h>
using namespace std;

// Generate all prime numbers less than n.
bool SieveOfEratosthenes(int n, bool isPrime[])
{
    // Initialize all entries of boolean array as true. A
    // value in isPrime[i] will finally be false if i is Not
    // a prime, else true bool isPrime[n+1];
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        isPrime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        
        // If isPrime[p] is not changed, then it is  a prime
        if (isPrime[p] == true) {
            
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
        }
    }
}

// Prints all super primes less than or equal to n.
vector<int> superPrimes(int n)
{
    // Generating primes using Sieve
    vector<int> ans ;
    bool isPrime[n + 1];
    SieveOfEratosthenes(n, isPrime);

    // Storing all the primes generated in a an array
    // primes[]
    int primes[n + 1], j = 0;
    for (int p = 2; p <= n; p++)
        if (isPrime[p])
            primes[j++] = p;

    // Printing all those prime numbers that occupy prime
    // numbered position in sequence of prime numbers.
    for (int k = 0; k < j; k++)
        if (isPrime[k + 1])
            ans.push_back(primes[k]);
            
    return ans; 
}


int main()
{
    int n = 241;
    vector<int> sPrimes = superPrimes(n);
    for( int i=0; i<sPrimes.size(); i++)
    {
        cout<<sPrimes[i]<<" "; 
    }
    return 0;
}

Java

// Generate all prime numbers less than n.
import java.util.*;

public class GfG {
    
    // Sieve of Eratosthenes algorithm
    public static void SieveOfEratosthenes(int n, boolean[] isPrime) {
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * 2; i <= n; i += p)
                    isPrime[i] = false;
            }
        }
    }

    // Prints all super primes less than or equal to n.
    public static List<Integer> superPrimes(int n) {
        List<Integer> ans = new ArrayList<>();
        boolean[] isPrime = new boolean[n + 1];
        SieveOfEratosthenes(n, isPrime);

        // Storing all the primes generated in a an array
        int[] primes = new int[n + 1];
        int j = 0;
        for (int p = 2; p <= n; p++)
            if (isPrime[p])
                primes[j++] = p;

        // Printing all those prime numbers that occupy 
        //prime numbered position in sequence of prime numbers.
        for (int k = 0; k < j; k++)
            if (isPrime[k + 1])
                ans.add(primes[k]);

        return ans;
    }

    public static void main(String[] args) {
        int n = 241;
        List<Integer> sPrimes = superPrimes(n);
        for (int prime : sPrimes) {
            System.out.print(prime + " ");
        }
    }
}

Python

# Generate all prime numbers less than n.
def SieveOfEratosthenes(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = isPrime[1] = False

    for p in range(2, int(n**0.5) + 1):
        if isPrime[p]:
            for i in range(p * 2, n + 1, p):
                isPrime[i] = False

    return isPrime

# Prints all super primes less than or equal to n.
def superPrimes(n):
    isPrime = SieveOfEratosthenes(n)
    primes = [i for i in range(n + 1) if isPrime[i]]
    ans = []

    for k in range(len(primes)):
        if k + 1 < len(isPrime) and isPrime[k + 1]:
            ans.append(primes[k])

    return ans

if __name__ == '__main__':
    n = 241
    sPrimes = superPrimes(n)
    print(' '.join(map(str, sPrimes)))

// Generate all prime numbers less than n.
using System;
using System.Collections.Generic;

class Program
{
    static void SieveOfEratosthenes(int n, bool[] isPrime)
    {
        // Initialize all entries of boolean array as true.
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            
            // If isPrime[p] is not changed, then it is a prime
            if (isPrime[p] == true) {
                
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p)
                    isPrime[i] = false;
            }
        }
    }

    // Prints all super primes less than or equal to n.
    static List<int> SuperPrimes(int n)
    {
        // Generating primes using Sieve
        List<int> ans = new List<int>();
        bool[] isPrime = new bool[n + 1];
        SieveOfEratosthenes(n, isPrime);

        // Storing all the primes generated in a an array
        int[] primes = new int[n + 1];
        int j = 0;
        for (int p = 2; p <= n; p++)
            if (isPrime[p])
                primes[j++] = p;

        // Printing all those prime numbers that occupy prime
        // numbered position in sequence of prime numbers.
        for (int k = 0; k < j; k++)
            if (isPrime[k + 1])
                ans.Add(primes[k]);

        return ans;
    }

    static void Main()
    {
        int n = 241;
        List<int> sPrimes = SuperPrimes(n);
        foreach (int prime in sPrimes)
        {
            Console.Write(prime + " ");
        }
    }
}

JavaScript

// Generate all prime numbers less than n.
function SieveOfEratosthenes(n) {
    
    // Initialize all entries of boolean array as true.
    let isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let p = 2; p * p <= n; p++) {
        
        // If isPrime[p] is not changed, then it is a prime
        if (isPrime[p] === true) {
            
            // Update all multiples of p
            for (let i = p * 2; i <= n; i += p)
                isPrime[i] = false;
        }
    }
    return isPrime;
}

// Prints all super primes less than or equal to n.
function superPrimes(n) {
    
    // Generating primes using Sieve
    let isPrime = SieveOfEratosthenes(n);
    let primes = [];

    // Storing all the primes generated in an array
    for (let p = 2; p <= n; p++)
        if (isPrime[p])
            primes.push(p);

    // Printing all those prime numbers that occupy prime
    // numbered position in sequence of prime numbers.
    let ans = [];
    for (let k = 0; k < primes.length; k++)
        if (isPrime[k + 1])
            ans.push(primes[k]);

    return ans;
}

let n = 241;
let sPrimes = superPrimes(n);
sPrimes.forEach(prime => {
    process.stdout.write(prime + " ");
});

Output

3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241

Time complexity : – O(n*log(log(n)))- Due to the use fo sieve of eratosthenis.
Auxiliary Space:- O(n) – due to the array used to store primes upro n.

Hardy-Ramanujan Theorem

Rahul Agrawal

Improve

Article Tags :

Practice Tags :

Super Prime

Similar Reads

Divisibility & Large Numbers

GCD and LCM

Series

Number Digits

Algebra

Number System

Prime Numbers & Primality Tests

Prime Factorization & Divisors

Modular Arithmetic

Thank You!

What kind of Experience do you want to share?