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