Pierpont Prime

Un primo de Pierpont es un número primo de la forma p = 2 ^l .3 ^k + 1. Los primeros números primos de Pierpont son 2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, …
Dado un número n , la tarea es imprimir números primos de Pierpont menores que n.
Ejemplos: 
 

Input : n = 15
Output : 2 3 5 7 13

Input : n = 200
Output : 2 3 5 7 13 17 19 37 
         73 97 109 163 193

La idea es encontrar números que tengan un factor de potencia de 2 y 3 solamente. Ahora, usando el tamiz de Eratóstenes , encuentre todos los números primos. Finalmente, imprima el número común de ambas secuencias.
A continuación se muestra la implementación de este enfoque: 
 

// CPP program to print Pierpont prime
// numbers smaller than n.
#include <bits/stdc++.h>
using namespace std;
 
bool printPierpont(int n)
{   
    // Finding all numbers having factor power
    // of 2 and 3 Using sieve
    bool arr[n+1];
    memset(arr, false, sizeof arr);
    int two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
 
    // Storing number of the form 2^i.3^k + 1.
    vector<int> v;
    for (int i = 0; i < n; i++)
        if (arr[i])
            v.push_back(i + 1);   
 
    // Finding prime number using sieve of
    // Eratosthenes. Reusing same array as
    // result of above computations in v.
    memset(arr, false, sizeof arr);
    for (int p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (int i = p * 2; i < n; i += p)
                arr[i] = true;
    }
 
    // Printing n pierpont primes smaller than n
    for (int i = 0; i < v.size(); i++)
        if (!arr[v[i]])
            cout << v[i] << " ";
}
 
// Driven Program
int main()
{
    int n = 200;
    printPierpont(n);
    return 0;
}

// Java program to print Pierpont prime
// numbers smaller than n.
import java.util.*;
class GFG{
static void printPierpont(int n)
{
    // Finding all numbers having factor power
    // of 2 and 3 Using sieve
    boolean[] arr=new boolean[n+1];
    int two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
 
    // Storing number of the form 2^i.3^k + 1.
    ArrayList<Integer> v=new ArrayList<Integer>();
    for (int i = 0; i < n; i++)
        if (arr[i])
            v.add(i + 1);
 
    // Finding prime number using sieve of
    // Eratosthenes. Reusing same array as
    // result of above computations in v.
    arr=new boolean[n+1];
    for (int p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (int i = p * 2; i < n; i += p)
                arr[i] = true;
    }
 
    // Printing n pierpont primes smaller than n
    for (int i = 0; i < v.size(); i++)
        if (!arr[v.get(i)])
            System.out.print(v.get(i)+" ");
}
 
// Driven Program
public static void main(String[] args)
{
    int n = 200;
    printPierpont(n);
}
}
// this code is contributed by mits

# Python3 program to print Pierpont
# prime numbers smaller than n.
 
def printPierpont(n):
 
    # Finding all numbers having factor
    # power of 2 and 3 Using sieve
    arr = [False] * (n + 1);
    two = 1;
    three = 1;
    while (two + 1 < n):
        arr[two] = True;
        while (two * three + 1 < n):
            arr[three] = True;
            arr[two * three] = True;
            three *= 3;
         
        three = 1;
        two *= 2;
 
    # Storing number of the form 2^i.3^k + 1.
    v = [];
    for i in range(n):
        if (arr[i]):
            v.append(i + 1);
 
    # Finding prime number using
    # sieve of Eratosthenes.
    # Reusing same array as result
    # of above computations in v.
    arr1 = [False] * (len(arr));
    p = 2;
    while (p * p < n):
        if (arr1[p] == False):
            for i in range(p * 2, n, p):
                arr1[i] = True;
        p += 1;
     
    # Printing n pierpont primes
    # smaller than n
    for i in range(len(v)):
        if (not arr1[v[i]]):
            print(v[i], end = " ");
 
# Driver Code
n = 200;
printPierpont(n);
 
# This code is contributed by mits

// C# program to print Pierpont prime
// numbers smaller than n.
using System;
using System.Collections;
 
class GFG{
static void printPierpont(int n)
{
    // Finding all numbers having factor power
    // of 2 and 3 Using sieve
    bool[] arr=new bool[n+1];
    int two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
 
    // Storing number of the form 2^i.3^k + 1.
    ArrayList v=new ArrayList();
    for (int i = 0; i < n; i++)
        if (arr[i])
            v.Add(i + 1);
 
    // Finding prime number using sieve of
    // Eratosthenes. Reusing same array as
    // result of above computations in v.
    arr=new bool[n+1];
    for (int p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (int i = p * 2; i < n; i += p)
                arr[i] = true;
    }
 
    // Printing n pierpont primes smaller than n
    for (int i = 0; i < v.Count; i++)
        if (!arr[(int)v[i]])
            Console.Write(v[i]+" ");
}
 
// Driven Program
static void Main()
{
    int n = 200;
    printPierpont(n);
}
}
// this code is contributed by mits

<?php
// PHP program to print
// Pierpont prime numbers
// smaller than n.
 
function printPierpont($n)
{
    // Finding all numbers
    // having factor power
    // of 2 and 3 Using sieve
    $arr = array_fill(0, $n + 1, false);
    $two = 1;
    $three = 1;
    while ($two + 1 < $n)
    {
        $arr[$two] = true;
        while ($two * $three + 1 < $n)
        {
            $arr[$three] = true;
            $arr[$two * $three] = true;
            $three *= 3;
        }
        $three = 1;
        $two *= 2;
    }
 
    // Storing number of the
    // form 2^i.3^k + 1.
    $v;
    $x = 0;
    for ($i = 0; $i < $n; $i++)
        if ($arr[$i])
            $v[$x++] = $i + 1;
 
    // Finding prime number using
    // sieve of Eratosthenes.
    // Reusing same array as result
    // of above computations in v.
    $arr1 = array_fill(0, count($arr), false);
    for ($p = 2;
         $p * $p < $n; $p++)
    {
        if ($arr1[$p] == false)
            for ($i = $p * 2;
                 $i < $n; $i += $p)
                $arr1[$i] = true;
    }
 
    // Printing n pierpont
    // primes smaller than n
    for ($i = 0; $i < $x; $i++)
        if (!$arr1[$v[$i]])
            echo $v[$i] . " ";
}
 
// Driver Code
$n = 200;
printPierpont($n);
 
// This Code is contributed by mits
?>

<script>
 
// Javascript program to print Pierpont prime
// numbers smaller than n.
 
function printPierpont(n)
{   
    // Finding all numbers having factor power
    // of 2 and 3 Using sieve
    var arr = Array(n+1).fill(false);
    var two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
 
    // Storing number of the form 2^i.3^k + 1.
    var v = [];
    for (var i = 0; i < n; i++)
        if (arr[i])
            v.push(i + 1);   
 
    // Finding prime number using sieve of
    // Eratosthenes. Reusing same array as
    // result of above computations in v.
    arr = Array(n+1).fill(false);
     
    for (var p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (var i = p * 2; i < n; i += p)
                arr[i] = true;
    }
 
    // Printing n pierpont primes smaller than n
    for (var i = 0; i < v.length; i++)
        if (!arr[v[i]])
            document.write( v[i] + " ");
}
 
// Driven Program
var n = 200;
printPierpont(n);
 
 
</script>

Producción:  

2 3 5 7 13 17 19 37 73 97 109 163 193

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.