Tamiz bit a bit

Dado un número n, imprima todos los números primos menores que n.
Ejemplos: 

Input : 30
Output : 2 3 5 7 11 13 17 19 23 29

Input : n = 100
Output : 2 3 5 7 11 13 17 19 23 29 31 37 
         41 43 47 53 59 61 67 71 73 79 83 
         89 97 

Sabemos calcular todos los números primos menores que n por la Criba de Eratóstenes . A continuación se muestra una implementación de Sieve. 
Una optimización en la implementación a continuación es que hemos saltado todos los números pares por completo.  
Reducimos el tamaño de la array principal a la mitad. También reducimos todas las iteraciones a la mitad. 

C++

// C++ program to implement normal Sieve
// of Eratosthenes using simple optimization
// to reduce size of prime array to half and
// reducing iterations.
#include <bits/stdc++.h>
using namespace std;
 
void normalSieve(int n)
{
    // prime[i] is going to store true if
    // if i*2 + 1 is composite.
    bool prime[n/2];
    memset(prime, false, sizeof(prime));
 
    // 2 is the only even prime so we can
    // ignore that. Loop starts from 3.
    for (int i=3 ; i*i < n; i+=2)
    {
        // If i is prime, mark all its
        // multiples as composite
        if (prime[i/2] == false)
            for (int j=i*i; j<n; j+=i*2)
                prime[j/2] = true;
    }
 
    // writing 2 separately
    printf("2 ");
 
    // Printing other primes
    for (int i=3; i<n ; i+=2)
        if (prime[i/2] == false)
            printf( "%d " , i );
}
 
// Driver code
int main()
{
    int n = 100 ;
    normalSieve(n);
    return 0;
}

Java

// Java program to implement normal Sieve
// of Eratosthenes using simple optimization
// to reduce size of prime array to half and
// reducing iterations.
import java.util.Arrays;
 
class GFG
{
    static void normalSieve(int n)
    {
        // prime[i] is going to store true if
        // if i*2 + 1 is composite.
        boolean prime[]=new boolean[n / 2];
        Arrays.fill(prime, false);
     
        // 2 is the only even prime so we can
        // ignore that. Loop starts from 3.
        for (int i = 3 ; i * i < n; i += 2)
        {
            // If i is prime, mark all its
            // multiples as composite
            if (prime[i / 2] == false)
                for (int j = i * i; j < n; j += i * 2)
                    prime[j / 2] = true;
        }
     
        // writing 2 separately
        System.out.print("2 ");
     
        // Printing other primes
        for (int i = 3; i < n ; i += 2)
            if (prime[i / 2] == false)
                System.out.print(i + " ");
    }
    public static void main (String[] args)
    {
        int n = 100 ;
        normalSieve(n);
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Sieve of Eratosthenes using
# simple optimization to reduce
# size of prime array to half and
# reducing iterations.
def normalSieve(n):
 
    # prime[i] is going to store
    # true if if i*2 + 1 is composite.
    prime = [0]*int(n / 2);
 
    # 2 is the only even prime so
    # we can ignore that. Loop
    # starts from 3.
    i = 3 ;
    while(i * i < n):
        # If i is prime, mark all its
        # multiples as composite
        if (prime[int(i / 2)] == 0):
            j = i * i;
            while(j < n):
                prime[int(j / 2)] = 1;
                j += i * 2;
        i += 2;
 
    # writing 2 separately
    print(2,end=" ");
 
    # Printing other primes
    i = 3;
    while(i < n):
        if (prime[int(i / 2)] == 0):
            print(i,end=" ");
        i += 2;
 
 
# Driver code
if __name__=='__main__':
    n = 100 ;
    normalSieve(n);
 
# This code is contributed by mits.

C#

// C# program to implement normal Sieve
// of Eratosthenes using simple optimization
// to reduce size of prime array to half and
// reducing iterations.
using System;
 
namespace prime
{
    public class GFG
    {    
                 
        public static void normalSieve(int n)
        {
             
        // prime[i] is going to store true if
        // if i*2 + 1 is composite.
        bool[] prime = new bool[n/2];
         
        for(int i = 0; i < n/2; i++)
            prime[i] = false;
         
        // 2 is the only even prime so we can
        // ignore that. Loop starts from 3.
        for(int i = 3; i*i < n; i = i+2)
        {
            // If i is prime, mark all its
            // multiples as composite
            if (prime[i / 2] == false)
             
                for (int j = i * i; j < n; j += i * 2)
                    prime[j / 2] = true;
        }
         
        // writing 2 separately
        Console.Write("2 ");
     
        // Printing other primes
        for (int i = 3; i < n ; i += 2)
         
            if (prime[i / 2] == false)
                Console.Write(i + " ");
             
        }
         
        // Driver Code
        public static void Main()
        {
        int n = 100;
        normalSieve(n);
        }
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP program to implement normal
// Sieve of Eratosthenes using
// simple optimization to reduce 
// size of prime array to half and
// reducing iterations.
function normalSieve($n)
{
    // prime[i] is going to store
    // true if if i*2 + 1 is composite.
    $prime = array_fill(0, (int)($n / 2),
                                  false);
 
    // 2 is the only even prime so
    // we can ignore that. Loop
    // starts from 3.
    for ($i = 3 ; $i * $i < $n; $i += 2)
    {
        // If i is prime, mark all its
        // multiples as composite
        if ($prime[$i / 2] == false)
            for ($j = $i * $i; $j < $n;
                          $j += $i * 2)
                $prime[$j / 2] = true;
    }
 
    // writing 2 separately
    echo "2 ";
 
    // Printing other primes
    for ($i = 3; $i < $n ; $i += 2)
        if ($prime[$i / 2] == false)
            echo $i . " ";
}
 
// Driver code
$n = 100 ;
normalSieve($n);
 
// This code is contributed by mits.
?>

Javascript

<script>
// javascript program to implement normal Sieve
// of Eratosthenes using simple optimization
// to reduce size of prime array to half and
// reducing iterations.
function normalSieve(n)
{
 
        // prime[i] is going to store true if
        // if i*2 + 1 is composite.
        var prime = Array(n / 2).fill(false);
         
 
        // 2 is the only even prime so we can
        // ignore that. Loop starts from 3.
        for (i = 3; i * i < n; i += 2)
        {
         
            // If i is prime, mark all its
            // multiples as composite
            if (prime[parseInt(i / 2)] == false)
                for (j = i * i; j < n; j += i * 2)
                    prime[parseInt(j / 2)] = true;
        }
 
        // writing 2 separately
        document.write("2 ");
 
        // Printing other primes
        for (i = 3; i < n; i += 2)
            if (prime[parseInt(i / 2)] == false)
                document.write(i + " ");
    }
     
        var n = 100;
        normalSieve(n);
 
// This code is contributed by todaysgaurav.
</script>

Producción : 
 

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

Complejidad de tiempo: O (nlogn)

Complejidad espacial: O(n)
Optimización adicional utilizando operadores bit a bit.  
La implementación anterior utiliza el tipo de datos bool que ocupa 1 byte. Podemos optimizar el espacio a n/8 usando bits individuales de un número entero para representar números primos individuales. Creamos una array de enteros de tamaño n/64. Tenga en cuenta que el tamaño de la array se reduce a n/64 desde n/2 (suponiendo que los números enteros toman 32 bits). 
 

C++

// C++ program to implement bitwise Sieve
// of Eratosthenes.
#include <bits/stdc++.h>
using namespace std;
 
// Checks whether x is prime or composite
bool ifnotPrime(int prime[], int x)
{
    // checking whether the value of element
    // is set or not. Using prime[x/64], we find
    // the slot in prime array. To find the bit
    // number, we divide x by 2 and take its mod
    // with 32.
    return (prime[x/64] & (1 << ((x >> 1) & 31)));
}
 
// Marks x composite in prime[]
bool makeComposite(int prime[], int x)
{
    // Set a bit corresponding to given element.
    // Using prime[x/64], we find the slot in prime
    // array. To find the bit number, we divide x
    // by 2 and take its mod with 32.
    prime[x/64] |= (1 << ((x >> 1) & 31));
}
 
// Prints all prime numbers smaller than n.
void bitWiseSieve(int n)
{
    // Assuming that n takes 32 bits, we reduce
    // size to n/64 from n/2.
    int prime[n/64];
 
    // Initializing values to 0 .
    memset(prime, 0, sizeof(prime));
 
    // 2 is the only even prime so we can ignore that
    // loop starts from 3 as we have used in sieve of
    // Eratosthenes .
    for (int i = 3; i * i <= n; i += 2) {
 
        // If i is prime, mark all its multiples as
        // composite
        if (!ifnotPrime(prime, i))
            for (int j = i * i, k = i << 1; j < n; j += k)
                makeComposite(prime, j);
    }
 
    // writing 2 separately
    printf("2 ");
 
    // Printing other primes
    for (int i = 3; i <= n; i += 2)
        if (!ifnotPrime(prime, i))
            printf("%d ", i);
}
 
// Driver code
int main()
{
    int n = 30;
    bitWiseSieve(n);
    return 0;
}

Java

// JAVA Code to implement Bitwise
// Sieve of Eratosthenes.
import java.util.*;
 
class GFG {
     
    // Checks whether x is prime or composite
    static int ifnotPrime(int prime[], int x)
    {
        // checking whether the value of element
        // is set or not. Using prime[x/64],
        // we find the slot in prime array.
        // To find the bit number, we divide x
        // by 2 and take its mod with 32.
        return (prime[x/64] & (1 << ((x >> 1) & 31)));
    }
      
    // Marks x composite in prime[]
    static void makeComposite(int prime[], int x)
    {
        // Set a bit corresponding to given element.
        // Using prime[x/64], we find the slot
        // in prime array. To find the bit number,
        // we divide x by 2 and take its mod with 32.
        prime[x/64] |= (1 << ((x >> 1) & 31));
    }
      
    // Prints all prime numbers smaller than n.
    static void bitWiseSieve(int n)
    {
        // Assuming that n takes 32 bits,
        // we reduce size to n/64 from n/2.
        int prime[] = new int[n/64 + 1];
      
      
        // 2 is the only even prime so we
        // can ignore that loop starts from
        // 3 as we have used in sieve of
        // Eratosthenes .
        for (int i = 3; i * i <= n; i += 2) {
      
            // If i is prime, mark all its
            // multiples as composite
            if (ifnotPrime(prime, i)==0)
                for (int j = i * i, k = i << 1;
                                  j < n; j += k)
                    makeComposite(prime, j);
        }
      
        // writing 2 separately
        System.out.printf("2 ");
      
        // Printing other primes
        for (int i = 3; i <= n; i += 2)
            if (ifnotPrime(prime, i) == 0)
                System.out.printf("%d ", i);
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int n = 30;
        bitWiseSieve(n);
    }
}
 
// This code is contributed by Arnav Kr. Mandal.   

Python3

# Python3 program to implement
# bitwise Sieve of Eratosthenes.
 
# Checks whether x is
# prime or composite
def ifnotPrime(prime, x):
 
    # Checking whether the value
    # of element is set or not.
    # Using prime[x/64], we find
    # the slot in prime array.
    # To find the bit we divide
    # x by 2 and take its mod
    # with 32.
    return (prime[int(x / 64)] &
           (1 << ((x >> 1) & 31)))
 
# Marks x composite in prime[]
def makeComposite(prime, x):
   
    # Set a bit corresponding to
    # given element. Using prime[x/64],
    # we find the slot in prime array. 
    # To find the bit number, we divide x
    # by 2 and take its mod with 32.
    prime[int(x / 64)] |=
    (1 << ((x >> 1) & 31))
 
# Prints all prime numbers
# smaller than n.
def bitWiseSieve(n):
 
    # Assuming that n takes 32 bits,
    # we reduce size to n/64 from n/2.
    # Initializing values to 0.
    prime = [0 for i in range(int(n / 64) + 1)]
 
    # 2 is the only even prime so
    # we can ignore that loop
    # starts from 3 as we have used 
    # in sieve of Eratosthenes
    for i in range(3, n + 1, 2):
        if(i * i <= n):
 
            # If i is prime, mark all
            # its multiples as composite
            if(ifnotPrime(prime, i)):
                continue
            else:
                k = i << 1               
                for j in range(i * i, n, k):
                    k = i << 1
                    makeComposite(prime, j)
                     
    # Writing 2 separately
    print("2 ", end = "")
 
    # Printing other primes
    for i in range(3, n + 1, 2):
        if(ifnotPrime(prime, i)):
            continue
        else:
            print(i, end = " ")
             
# Driver code
n = 30
bitWiseSieve(n)
 
# This code is contributed by avanitrachhadiya2155

C#

// C# Code to implement Bitwise
// Sieve of Eratosthenes.
using System;
 
class GFG
{
 
// Checks whether x is
// prime or composite
static int ifnotPrime(int[] prime, int x)
{
    // checking whether the value
    // of element is set or not.
    // Using prime[x/64], we find
    // the slot in prime array.
    // To find the bit number, we
    // divide x by 2 and take its
    // mod with 32.
    return (prime[x / 64] &
           (1 << ((x >> 1) & 31)));
}
 
// Marks x composite in prime[]
static void makeComposite(int[] prime,
                          int x)
{
    // Set a bit corresponding to
    // given element. Using prime[x/64],
    // we find the slot in prime array.
    // To find the bit number, we divide
    // x by 2 and take its mod with 32.
    prime[x / 64] |= (1 << ((x >> 1) & 31));
}
 
// Prints all prime numbers
// smaller than n.
static void bitWiseSieve(int n)
{
    // Assuming that n takes 32 bits,
    // we reduce size to n/64 from n/2.
    int[] prime = new int[(int)(n / 64) + 1];
 
 
    // 2 is the only even prime so we
    // can ignore that loop starts from
    // 3 as we have used in sieve of
    // Eratosthenes .
    for (int i = 3; i * i <= n; i += 2)
    {
 
        // If i is prime, mark all its
        // multiples as composite
        if (ifnotPrime(prime, i) == 0)
            for (int j = i * i, k = i << 1;
                             j < n; j += k)
                makeComposite(prime, j);
    }
 
    // writing 2 separately
    Console.Write("2 ");
 
    // Printing other primes
    for (int i = 3; i <= n; i += 2)
        if (ifnotPrime(prime, i) == 0)
            Console.Write(i + " ");
}
 
// Driver Code
static void Main()
{
    int n = 30;
    bitWiseSieve(n);
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP program to implement
// bitwise Sieve of Eratosthenes.
$prime;
 
// Checks whether x is
// prime or composite
function ifnotPrime($x)
{
    global $prime;
     
    // checking whether the value
    // of element is set or not.
    // Using prime[x/64], we find
    // the slot in prime array.
    // To find the bit number, we
    // divide x by 2 and take its
    // mod with 32.
    return $a = ($prime[(int)($x / 64)] &
                        (1 << (($x >> 1) & 31)));
}
 
// Marks x composite in prime[]
function makeComposite($x)
{
    global $prime;
     
    // Set a bit corresponding to
    // given element. Using prime[x/64],
    // we find the slot in prime
    // array. To find the bit number,
    // we divide x by 2 and take its
    // mod with 32.
    $prime[(int)($x / 64)] |=
                (1 << (($x >> 1) & 31));
}
 
// Prints all prime
// numbers smaller than n.
function bitWiseSieve($n)
{
    global $prime;
     
    // Assuming that n takes
    // 32 bits, we reduce
    // size to n/64 from n/2.
    // Initializing values to 0 .
    $prime = array_fill(0,
                   (int)ceil($n / 64), 0);
                    
    // 2 is the only even prime
    // so we can ignore that
    // loop starts from 3 as we
    // have used in sieve of
    // Eratosthenes .
    for ($i = 3; $i * $i <= $n; $i += 2)
    {
 
        // If i is prime, mark
        // all its multiples as
        // composite
        if (!ifnotPrime($i))
            for ($j = $i * $i,
                 $k = $i << 1;
                 $j < $n; $j += $k)
                makeComposite($j);
    }
 
    // writing 2 separately
    echo "2 ";
 
    // Printing other primes
    for ($i = 3; $i <= $n; $i += 2)
        if (!ifnotPrime($i))
            echo $i." ";
}
 
// Driver code
$n = 30;
bitWiseSieve($n);
 
// This code is contributed
// by mits.
?>

Javascript

<script>
 
// javascript Code to implement Bitwise
// Sieve of Eratosthenes.
    
// Checks whether x is prime or composite
function ifnotPrime(prime , x)
{
    // checking whether the value of element
    // is set or not. Using prime[x/64],
    // we find the slot in prime array.
    // To find the bit number, we divide x
    // by 2 and take its mod with 32.
    return (prime[x/64] & (1 << ((x >> 1) & 31)));
}
  
// Marks x composite in prime
function makeComposite(prime , x)
{
    // Set a bit corresponding to given element.
    // Using prime[x/64], we find the slot
    // in prime array. To find the bit number,
    // we divide x by 2 and take its mod with 32.
    prime[x/64] |= (1 << ((x >> 1) & 31));
}
  
// Prints all prime numbers smaller than n.
function bitWiseSieve(n)
{
    // Assuming that n takes 32 bits,
    // we reduce size to n/64 from n/2.
    var prime = Array.from({length: (n/64 + 1)}, (_, i) => 0);
  
  
    // 2 is the only even prime so we
    // can ignore that loop starts from
    // 3 as we have used in sieve of
    // Eratosthenes .
    for (var i = 3; i * i <= n; i += 2) {
  
        // If i is prime, mark all its
        // multiples as composite
        if (ifnotPrime(prime, i)==0)
            for (var j = i * i, k = i << 1;
                              j < n; j += k)
                makeComposite(prime, j);
    }
  
    // writing 2 separately
    document.write("2 ");
  
    // Printing other primes
    for (var i = 3; i <= n; i += 2)
        if (ifnotPrime(prime, i) == 0)
            document.write(i+" ");
}
 
/* Driver program to test above function */
var n = 30;
bitWiseSieve(n);  
 
// This code is contributed by 29AjayKumar
</script>

Producción: 
 

2 3 5 7 11 13 17 19 23 29

Complejidad de tiempo: O (nlogn)

Complejidad espacial: O(n)

Publicación traducida automáticamente

Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *