Primos alternos hasta N

Tenemos que imprimir números primos alternos hasta N.
Ejemplos: 
 

Input : N = 10
Output : 2 5 

Input : N = 15
Output : 2 5 11 

Enfoque ingenuo: podemos simplemente iterar sobre N y verificar si el número es primo o no e imprimir el número alternativo simplemente manteniendo una variable de indicador de alteración simple.
 

/* C++ program to print all
primes smaller than or
equal to n using Naive approach.*/
#include<bits/stdc++.h>
using namespace std;
 
/* Function for checking
number is prime or not */
int prime(int num)
{
    int i, flag = 0;
    for(i = 2; i<= num / 2; i++)
    {
        if(num % i == 0)
        {
            flag = 1;
            break;
        }
    }
     
    // if flag = 0 then number
    // is prime and return 1
    // otherwise return 0
    if(flag == 0)
        return 1;
    else
        return 0;
}
 
// Function for printing
// alternate prime number
void print_alternate_prime(int n)
{
    // counter is initialize with 0
    int counter = 0;
 
    // looping through 2 to n-1
    for(int num = 2; num < n; num++)
    {
        // function calling along
        // with if condition
        if (prime(num) == 1)
        {
            // if counter is multiple of 2
            // then only print prime number
            if (counter % 2 == 0)
                cout << num << " ";
                 
            counter ++;
        }
    }
}
 
// Driver code
int main()
{
    int n = 15;
    cout << "Following are the alternate prime"
         << " number smaller than or equal to "
         << n << endl;
          
    // Function calling
    print_alternate_prime(n);
}
         
// This code is contributed
// by ChitraNayal

// Java program to print all
// primes smaller than or
// equal to n using Naive approach.
class GFG
{
     
/* Function for checking
number is prime or not */
static int prime(int num)
{
int i, flag = 0;
for(i = 2; i<= num / 2; i++)
{
    if(num % i == 0)
    {
        flag = 1;
        break;
    }
}
 
// if flag = 0 then number is prime
// and return 1 otherwise return 0
if(flag == 0)
    return 1;
else
    return 0;
}
 
// Function for printing
// alternate prime number
static void print_alternate_prime(int n)
{
// counter is initialize with 0
int counter = 0;
 
// looping through 2 to n-1
for(int num = 2; num < n; num++)
{
    // function calling along
    // with if condition
    if (prime(num) == 1)
    {
        // if counter is multiple of 2
        // then only print prime number
        if (counter % 2 == 0)
            System.out.print(num + " ");
                 
        counter ++;
    }
}
}
 
// Driver code
public static void main(String[] args)
{
    int n = 15;
    System.out.println("Following are the alternate " +
                         "prime number smaller than " +
                                   "or equal to " + n);
 
    // Function calling
    print_alternate_prime(n);
}
}
 
// This code is contributed
// by ChitraNayal

# Python3 program to print all
# primes smaller than or
# equal to n using Naive approach.
 
# Function for checking number
# is prime or not
def prime(num) :
    flag = 0
    for i in range(2,num // 2 + 1) :
        if num % i == 0 :
            flag = 1
            break
    # if flag = 0 then number is prime
    # and return 1 otherwise return 0
    if flag == 0 :
        return 1
    else :
        return 0
 
# Function for printing alternate prime number
def print_alternate_prime(n):
     
    # counter is initialize with 0
    counter = 0
 
    # looping through 2 to n-1
    for num in range(2,n) :
         
        # function calling along with if condition
        if prime(num) == 1 :
             
            # if counter is multiple of 2 then
            # only print prime number
            if counter % 2 == 0 :
                print(num,end =" ")
                 
            counter += 1
 
# Driver code
if __name__ == "__main__":
    n = 15
    print("Following are the alternate prime"
          +"number smaller than or equal to",n)
 
          
 
    # Function calling
    print_alternate_prime(n)
        

// C# program to print all
// primes smaller than or
// equal to n using Naive approach.
using System;
class GFG
{
/* Function for checking
number is prime or not */
static int prime(int num)
{
int i, flag = 0;
for(i = 2; i <= num / 2; i++)
{
    if(num % i == 0)
    {
        flag = 1;
        break;
    }
}
 
// if flag = 0 then number is prime
// and return 1 otherwise return 0
if(flag == 0)
    return 1;
else
    return 0;
}
 
// Function for printing
// alternate prime number
static void print_alternate_prime(int n)
{
// counter is initialize with 0
int counter = 0;
 
// looping through 2 to n-1
for(int num = 2; num < n; num++)
{
    // function calling along
    // with if condition
    if (prime(num) == 1)
    {
        // if counter is multiple of 2
        // then only print prime number
        if (counter % 2 == 0)
            Console.Write(num + " ");
                 
        counter ++;
    }
}
}
 
// Driver code
public static void Main()
{
    int n = 15;
    Console.Write("Following are the alternate " +
                    "prime number smaller than " +
                       "or equal to " + n + "\n");
 
    // Function calling
    print_alternate_prime(n);
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to print all
// primes smaller than or
// equal to n using Naive approach.
 
// Function for checking number
// is prime or not
function prime($num)
{
    $flag = 0;
    for($i = 2; $i <= $num / 2; $i++)
    {
        if ($num % $i == 0)
        {
            $flag = 1;
            break;
        }
    }
     
    // if flag = 0 then number is prime
    // and return 1 otherwise return 0
    if ($flag == 0)
        return 1;
    else
        return 0;
}
 
// Function for printing
// alternate prime number
function print_alternate_prime($n)
{
     
    // counter is initialize with 0
    $counter = 0;
 
    // looping through 2 to n-1
    for($num = 2; $num < $n; $num++)
    {
        // function calling along
        // with if condition
        if(prime($num) == 1)
        {
            // if counter is multiple of 2
            // then only print prime number
            if ($counter % 2 == 0 )
                echo $num . " ";
                 
            $counter += 1;
        }
    }
}
 
// Driver code
$n = 15;
echo "Following are the alternate prime ".
      "number smaller than or equal to " .
                                $n . "\n";
// Function calling
print_alternate_prime($n);
 
// This code is contributed
// by ChitraNayal
?>

<script>
// javascript program to print all
// primes smaller than or
// equal to n using Naive approach.   
/*
     * Function for checking number is prime or not
     */
    function prime(num) {
        var i, flag = 0;
        for (i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                flag = 1;
                break;
            }
        }
 
        // if flag = 0 then number is prime
        // and return 1 otherwise return 0
        if (flag == 0)
            return 1;
        else
            return 0;
    }
 
    // Function for printing
    // alternate prime number
    function print_alternate_prime(n)
    {
     
        // counter is initialize with 0
        var counter = 0;
 
        // looping through 2 to n-1
        for (num = 2; num < n; num++)
        {
         
            // function calling along
            // with if condition
            if (prime(num) == 1)
            {
             
                // if counter is multiple of 2
                // then only print prime number
                if (counter % 2 == 0)
                    document.write(num + " ");
 
                counter++;
            }
        }
    }
 
    // Driver code
    var n = 15;
    document.write("Following are the alternate " + "prime number smaller than " + "or equal to " + n+"<br/>");
 
    // Function calling
    print_alternate_prime(n);
 
// This code is contributed by Rajput-Ji
</script>

Following are the alternate prime numbers smaller  than or equal to 15
2 5 11

Complejidad de tiempo: O(N *  )
Enfoque eficiente: Usando el tamiz de Eratóstenes , podemos imprimir todos los valores verdaderos alternativos en el tamiz.
 

// C++ program to print all primes smaller than or
// equal to n using Sieve of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
 
void SieveOfEratosthenes(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
    bool flag = true;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            if (flag) {
                cout << p << " ";
                flag = false;
            }
            else {
 
                // for next prime to get printed
                flag = true;
            }
        }
    }
}
 
// Driver Program to test above function
int main()
{
    int n = 15;
    cout << "Following are the alternate"
         << " prime numbers smaller "
         << " than or equal to " << n << endl;
    SieveOfEratosthenes(n);
    return 0;
}

// Java program to print all primes
// smaller than or equal to n using
// Sieve of Eratosthenes
class GFG
{
static void SieveOfEratosthenes(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 < prime.length; 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
boolean flag = true;
for (int p = 2; p <= n; p++)
{
    if (prime[p])
    {
        if (flag)
        {
            System.out.print(p + " ");
            flag = false;
        }
        else
        {
 
            // for next prime
            // to get printed
            flag = true;
        }
    }
}
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 15;
    System.out.println("Following are the alternate" +
                           " prime numbers smaller " +
                            "than or equal to " + n );
    SieveOfEratosthenes(n);
}
}
 
// This code is contributed
// by ChitraNayal

# Python 3 program to print all
# equal to n using Sieve of Eratosthenes
 
def SieveOfEratosthenes(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 = [None] * (n + 1)
    for i in range(len(prime)):
        prime[i] = True
 
    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
    flag = True
    for p in range(2, n + 1):
        if (prime[p]):
            if (flag):
                print(str(p), end = " ")
                flag = False
             
            else:
 
                # for next prime to get printed
                flag = True
 
# Driver Code
if __name__ == "__main__":
    n = 15
    print("Following are the alternate" +
              " prime numbers smaller " +
            "than or equal to " + str(n))
    SieveOfEratosthenes(n)
 
# This code is contributed
# by ChitraNayal

// C# program to print all primes
// smaller than or equal to n using
// Sieve of Eratosthenes
using System;
 
class GFG
{
static void SieveOfEratosthenes(int n)
{
     
// Create a bool 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 < prime.Length; 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
bool flag = true;
for (int p = 2; p <= n; p++)
{
    if (prime[p])
    {
        if (flag)
        {
            Console.Write(p + " ");
            flag = false;
        }
        else
        {
 
            // for next prime to
            // get printed
            flag = true;
        }
    }
}
}
 
// Driver Code
public static void Main()
{
    int n = 15;
    Console.Write("Following are the alternate" +
                      " prime numbers smaller " +
                 "than or equal to " + n + "\n");
    SieveOfEratosthenes(n);
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to print all
// primes smaller than or
// equal to n using Sieve
// of Eratosthenes
function SieveOfEratosthenes($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();
    for( $i = 0; $i <= $n; $i++)
        $prime[$i] = 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
    $flag = true;
    for ($p = 2; $p <= $n; $p++)
    {
        if ($prime[$p])
        {
            if ($flag)
            {
                echo $p . " ";
                $flag = false;
            }
            else
            {
 
                // for next prime to
                // get printed
                $flag = true;
            }
        }
    }
}
 
// Driver Code
$n = 15;
echo "Following are the alternate".
         " prime numbers smaller ".
   "than or equal to " . $n . "\n";
SieveOfEratosthenes($n);
 
// This code is contributed
// by ChitraNayal
?>

<script>
// Javascript program to print all primes
// smaller than or equal to n using
// Sieve of Eratosthenes
 
function SieveOfEratosthenes(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 < prime.length; 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
let flag = true;
for (let p = 2; p <= n; p++)
{
    if (prime[p])
    {
        if (flag)
        {
            document.write(p + " ");
            flag = false;
        }
        else
        {
  
            // for next prime
            // to get printed
            flag = true;
        }
    }
}
}
 
// Driver Code
let  n = 15;
document.write("Following are the alternate" +
                           " prime numbers smaller " +
                            "than or equal to " + n +"<br>");
     
SieveOfEratosthenes(n);
// This code is contributed by avanitrachhadiya2155
</script>

Following are the alternate prime numbers smaller  than or equal to 15
2 5 11

Complejidad de tiempo: O( *log(log(N))) para aplicar tamizado y O(N) para atravesar el tamiz.