Genera todos los números primos entre dos números dados. La tarea es imprimir números primos en ese rango. La criba de Eratóstenes es una de las formas más eficientes de encontrar todos los números primos menores que n, donde n es menor que 10 millones más o menos.
Ejemplos:
Input : start = 50 end = 100 Output : 53 59 61 67 71 73 79 83 89 97 Input : start = 900 end = 1000 Output : 907 911 919 929 937 941 947 953 967 971 977 983 991 997
La idea es usar Tamiz de Eratóstenes como subrutina. Hemos discutido una implementación en números primos en un rango dado usando STL | Serie 1
- Encuentre primos en el rango de 0 al final y guárdelo en un vector
- Encuentre el índice del elemento menor que el valor inicial usando la búsqueda binaria. Usamos lower_bound() en STL .
- Borra elementos desde el principio del vector hasta ese índice. Usamos borrado vectorial()
¡Viola! El vector contiene primos que van desde el principio hasta el final.
// C++ program to print all primes
// in a range using Sieve of Eratosthenes
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
#define all(v) v.begin(), v.end()
typedef unsigned long long int ulli;
vector<ulli> sieve(ulli n)
{
// Create a boolean vector "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.
vector<bool> prime(n + 1, true);
prime[0] = false;
prime[1] = false;
int m = sqrt(n);
for (ulli p = 2; p <= m; p++) {
// If prime[p] is not changed, then it
// is a prime
if (prime[p]) {
// Update all multiples of p
for (ulli i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// push all the primes into the vector ans
vector<ulli> ans;
for (int i = 0; i < n; i++)
if (prime[i])
ans.push_back(i);
return ans;
}
vector<ulli> sieveRange(ulli start, ulli end)
{
// find primes from [0..end] range
vector<ulli> ans = sieve(end);
// Find index of first prime greater than or
// equal to start
// O(sqrt(n)loglog(n))
int lower_bound_index = lower_bound(all(ans), start) -
ans.begin();
// Remove all elements smaller than start.
// O(logn)
ans.erase(ans.begin(), ans.begin() + lower_bound_index);
return ans;
}
// Driver Program to test above function
int main(void)
{
ulli start = 50;
ulli end = 100;
vector<ulli> ans = sieveRange(start, end);
for (auto i : ans)
cout << i << ' ';
return 0;
}
Producción:
53 59 61 67 71 73 79 83 89 97
Publicación traducida automáticamente
Artículo escrito por Varun Thakur y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA