Dado un número n, imprima todos los números primos menores que n. Por ejemplo, si el número dado es 10, genera 2, 3, 5, 7.
Un enfoque ingenuo es ejecutar un ciclo de 0 a n-1 y verificar la primacía de cada número. Un mejor enfoque es usar el tamiz simple de Eratóstenes .
C
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
bool mark[limit];
for(int i = 0; i<limit; i++) {
mark[i] = true;
}
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
if (mark[p] == true)
cout << p << " ";
}
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
bool mark[limit];
for(int i = 0; i<limit; i++) {
mark[i] = true;
}
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
if (mark[p] == true)
cout << p << " ";
}
// This code is contributed by sanjoy_62.
Java
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
static void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
boolean []mark = new boolean[limit];
Arrays.fill(mark, true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
if (mark[p] == true)
System.out.print(p + " ");
}
// This code is contributed by rutvik_56.
Python3
# This functions finds all primes smaller than 'limit' # using simple sieve of eratosthenes. def simpleSieve(limit): # Create a boolean array "mark[0..limit-1]" and # initialize all entries of it as true. A value # in mark[p] will finally be false if 'p' is Not # a prime, else true. mark = [True for i in range(limit)] # One by one traverse all numbers so that their # multiples can be marked as composite. for p in range(p * p, limit - 1, 1): # If p is not changed, then it is a prime if (mark[p] == True): # Update all multiples of p for i in range(p * p, limit - 1, p): mark[i] = False # Print all prime numbers and store them in prime for p in range(2, limit - 1, 1): if (mark[p] == True): print(p, end=" ") # This code is contributed by Dharanendra L V.
C#
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
static void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
bool []mark = new bool[limit];
Array.Fill(mark, true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
if (mark[p] == true)
Console.Write(p + " ");
}
// This code is contributed by pratham76.
Javascript
<script>
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
function simpleSieve(limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
var mark = Array(limit).fill(true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (p = 2; p < limit; p++)
if (mark[p] == true)
document.write(p + " ");
}
// This code is contributed by todaysgaurav
</script>
Problemas con la criba simple:
la criba de Eratóstenes se ve bien, pero considere la situación cuando n es grande, la criba simple enfrenta los siguientes problemas.
- Una array de tamaño Θ(n) puede no caber en la memoria
- El tamiz simple no se almacena en caché incluso para n ligeramente más grandes. El algoritmo atraviesa la array sin localidad de referencia.
Tamiz segmentado
La idea de un tamiz segmentado es dividir el rango [0..n-1] en diferentes segmentos y calcular los números primos en todos los segmentos uno por uno. Este algoritmo primero usa Simple Sieve para encontrar números primos menores o iguales a √(n). A continuación se muestran los pasos utilizados en el tamiz segmentado.
- Use Simple Sieve para encontrar todos los números primos hasta la raíz cuadrada de ‘n’ y almacene estos números primos en una array «prime[]». Almacene los primos encontrados en una array ‘prime[]’.
- Necesitamos todos los primos en el rango [0..n-1]. Dividimos este rango en diferentes segmentos de modo que el tamaño de cada segmento sea como máximo √n
- Haz lo siguiente para cada segmento [bajo..alto]
- Cree una marca de array [alto-bajo + 1]. Aquí solo necesitamos el espacio O(x) donde x es un número de elementos en un rango dado.
- Repita todos los números primos encontrados en el paso 1. Para cada número primo, marque sus múltiplos en el rango dado [bajo…alto].
En Simple Sieve, necesitábamos un espacio O(n) que puede no ser factible para n grande. Aquí necesitamos el espacio O(√n) y procesamos rangos más pequeños a la vez (localidad de referencia)
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print all primes smaller than
// n using segmented sieve
#include <bits/stdc++.h>
using namespace std;
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes. It also stores
// found primes in vector prime[]
void simpleSieve(int limit, vector<int> &prime)
{
// Create a boolean array "mark[0..n-1]" and initialize
// all entries of it as true. A value in mark[p] will
// finally be false if 'p' is Not a prime, else true.
vector<bool> mark(limit + 1, true);
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
{
if (mark[p] == true)
{
prime.push_back(p);
cout << p << " ";
}
}
}
// Prints all prime numbers smaller than 'n'
void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = floor(sqrt(n))+1;
vector<int> prime;
prime.reserve(limit);
simpleSieve(limit, prime);
// Divide the range [0..n-1] in different segments
// We have chosen segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range. A value in mark[i]
// will finally be false if 'i-low' is Not a prime,
// else true.
bool mark[limit+1];
memset(mark, true, sizeof(mark));
// Use the found primes by simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.size(); i++)
{
// Find the minimum number in [low..high] that is
// a multiple of prime[i] (divisible by prime[i])
// For example, if low is 31 and prime[i] is 3,
// we start with 33.
int loLim = floor(low/prime[i]) * prime[i];
if (loLim < low)
loLim += prime[i];
/* Mark multiples of prime[i] in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j=loLim; j<high; j+=prime[i])
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i<high; i++)
if (mark[i - low] == true)
cout << i << " ";
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver program to test above function
int main()
{
int n = 100000;
cout << "Primes smaller than " << n << ":n";
segmentedSieve(n);
return 0;
}
Java
// Java program to print all primes smaller than
// n using segmented sieve
import java.util.Vector;
import static java.lang.Math.sqrt;
import static java.lang.Math.floor;
class Test
{
// This method finds all primes smaller than 'limit'
// using simple sieve of eratosthenes. It also stores
// found primes in vector prime[]
static void simpleSieve(int limit, Vector<Integer> prime)
{
// Create a boolean array "mark[0..n-1]" and initialize
// all entries of it as true. A value in mark[p] will
// finally be false if 'p' is Not a prime, else true.
boolean mark[] = new boolean[limit+1];
for (int i = 0; i < mark.length; i++)
mark[i] = true;
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
{
if (mark[p] == true)
{
prime.add(p);
System.out.print(p + " ");
}
}
}
// Prints all prime numbers smaller than 'n'
static void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = (int) (floor(sqrt(n))+1);
Vector<Integer> prime = new Vector<>();
simpleSieve(limit, prime);
// Divide the range [0..n-1] in different segments
// We have chosen segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range. A value in mark[i]
// will finally be false if 'i-low' is Not a prime,
// else true.
boolean mark[] = new boolean[limit+1];
for (int i = 0; i < mark.length; i++)
mark[i] = true;
// Use the found primes by simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.size(); i++)
{
// Find the minimum number in [low..high] that is
// a multiple of prime.get(i) (divisible by prime.get(i))
// For example, if low is 31 and prime.get(i) is 3,
// we start with 33.
int loLim = (int) (floor(low/prime.get(i)) * prime.get(i));
if (loLim < low)
loLim += prime.get(i);
/* Mark multiples of prime.get(i) in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j=loLim; j<high; j+=prime.get(i))
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i<high; i++)
if (mark[i - low] == true)
System.out.print(i + " ");
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver method
public static void main(String args[])
{
int n = 100;
System.out.println("Primes smaller than " + n + ":");
segmentedSieve(n);
}
}
Python3
# Python3 program to print all primes
# smaller than n, using segmented sieve
import math
prime = []
# This method finds all primes
# smaller than 'limit' using
# simple sieve of eratosthenes.
# It also stores found primes in list prime
def simpleSieve(limit):
# Create a boolean list "mark[0..n-1]" and
# initialize all entries of it as True.
# A value in mark[p] will finally be False
# if 'p' is Not a prime, else True.
mark = [True for i in range(limit + 1)]
p = 2
while (p * p <= limit):
# If p is not changed, then it is a prime
if (mark[p] == True):
# Update all multiples of p
for i in range(p * p, limit + 1, p):
mark[i] = False
p += 1
# Print all prime numbers
# and store them in prime
for p in range(2, limit):
if mark[p]:
prime.append(p)
print(p,end = " ")
# Prints all prime numbers smaller than 'n'
def segmentedSieve(n):
# Compute all primes smaller than or equal
# to square root of n using simple sieve
limit = int(math.floor(math.sqrt(n)) + 1)
simpleSieve(limit)
# Divide the range [0..n-1] in different segments
# We have chosen segment size as sqrt(n).
low = limit
high = limit * 2
# While all segments of range [0..n-1] are not processed,
# process one segment at a time
while low < n:
if high >= n:
high = n
# To mark primes in current range. A value in mark[i]
# will finally be False if 'i-low' is Not a prime,
# else True.
mark = [True for i in range(limit + 1)]
# Use the found primes by simpleSieve()
# to find primes in current range
for i in range(len(prime)):
# Find the minimum number in [low..high]
# that is a multiple of prime[i]
# (divisible by prime[i])
# For example, if low is 31 and prime[i] is 3,
# we start with 33.
loLim = int(math.floor(low / prime[i]) *
prime[i])
if loLim < low:
loLim += prime[i]
# Mark multiples of prime[i] in [low..high]:
# We are marking j - low for j, i.e. each number
# in range [low, high] is mapped to [0, high-low]
# so if range is [50, 100] marking 50 corresponds
# to marking 0, marking 51 corresponds to 1 and
# so on. In this way we need to allocate space
# only for range
for j in range(loLim, high, prime[i]):
mark[j - low] = False
# Numbers which are not marked as False are prime
for i in range(low, high):
if mark[i - low]:
print(i, end = " ")
# Update low and high for next segment
low = low + limit
high = high + limit
# Driver Code
n = 100
print("Primes smaller than", n, ":")
segmentedSieve(100)
# This code is contributed by bhavyadeep
C#
// C# program to print
// all primes smaller than
// n using segmented sieve
using System;
using System.Collections;
class GFG
{
// This method finds all primes
// smaller than 'limit' using simple
// sieve of eratosthenes. It also stores
// found primes in vector prime[]
static void simpleSieve(int limit,
ArrayList prime)
{
// Create a boolean array "mark[0..n-1]"
// and initialize all entries of it as
// true. A value in mark[p] will finally be
// false if 'p' is Not a prime, else true.
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
{
if (mark[p] == true)
{
prime.Add(p);
Console.Write(p + " ");
}
}
}
// Prints all prime numbers smaller than 'n'
static void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);
ArrayList prime = new ArrayList();
simpleSieve(limit, prime);
// Divide the range [0..n-1] in
// different segments We have chosen
// segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range
// [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range.
// A value in mark[i] will finally
// be false if 'i-low' is Not a prime,
// else true.
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
// Use the found primes by
// simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.Count; i++)
{
// Find the minimum number in
// [low..high] that is a multiple
// of prime.get(i) (divisible by
// prime.get(i)) For example,
// if low is 31 and prime.get(i)
// is 3, we start with 33.
int loLim = ((int)Math.Floor((double)(low /
(int)prime[i])) * (int)prime[i]);
if (loLim < low)
loLim += (int)prime[i];
/* Mark multiples of prime.get(i) in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j = loLim; j < high; j += (int)prime[i])
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i < high; i++)
if (mark[i - low] == true)
Console.Write(i + " ");
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver code
static void Main()
{
int n = 100;
Console.WriteLine("Primes smaller than " + n + ":");
segmentedSieve(n);
}
}
// This code is contributed by mits
Javascript
// JavaSCript program to print all primes smaller than
// n using segmented sieve
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes. It also stores
// found primes in vector prime[]
let res = "";
function simpleSieve(limit, prime)
{
// Create a boolean array "mark[0..n-1]" and initialize
// all entries of it as true. A value in mark[p] will
// finally be false if 'p' is Not a prime, else true.
let mark = new Array(limit+1).fill(true);
for (let p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] === true)
{
// Update all multiples of p
for (let i=p*p; i<limit; i+=p){
mark[i] = false;
}
}
}
// Print all prime numbers and store them in prime
for (let p=2; p<limit; p++)
{
if (mark[p] === true)
{
prime.push(p);
res = res + p + " ";
}
}
}
// Prints all prime numbers smaller than 'n'
function segmentedSieve(n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
let limit = Math.floor(Math.sqrt(n))+1;
let prime = new Array(limit);
simpleSieve(limit, prime);
// Divide the range [0..n-1] in different segments
// We have chosen segment size as sqrt(n).
let low = limit;
let high = 2*limit;
// While all segments of range [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n){
high = n;
}
// To mark primes in current range. A value in mark[i]
// will finally be false if 'i-low' is Not a prime,
// else true.
let mark = new Array(limit+1).fill(true);
// Use the found primes by simpleSieve() to find
// primes in current range
for (let i = 0; i < prime.length; i++)
{
// Find the minimum number in [low..high] that is
// a multiple of prime[i] (divisible by prime[i])
// For example, if low is 31 and prime[i] is 3,
// we start with 33.
let loLim = Math.floor(low/prime[i]) * prime[i];
if (loLim < low){
loLim += prime[i];
}
/* Mark multiples of prime[i] in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (let j=loLim; j<high; j+=prime[i]){
mark[j-low] = false;
}
}
// Numbers which are not marked as false are prime
for (let i = low; i<high; i++){
if (mark[i - low] == true){
res = res + i + " ";
}
}
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
console.log(res);
}
// Driver program to test above function
let n = 100;
console.log("Primes smaller than", n);
segmentedSieve(n);
// The code is contributed by Gautam goel (gautamgoel962)
Producción:
Primes smaller than 100: 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 del tiempo: O(sqrt(n))
Espacio Auxiliar: O(1)
Tenga en cuenta que la complejidad del tiempo (o una cantidad de operaciones) por Segmented Sieve es la misma que Simple Sieve . Tiene ventajas para grandes ‘n’ ya que tiene una mejor localidad de referencia, lo que permite un mejor almacenamiento en caché por parte de la CPU y también requiere menos espacio de memoria.
Este artículo es una contribución de Utkarsh Trivedi. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA