M1n021
Utente Attivo
- Messaggi
- 194
- Reazioni
- 84
- Punteggio
- 41
Ciao a tutti, sulla scia di un recente topic ho deciso di scrivere una funzione
Per la precisione ho provato ad implementare una sorta di crivello di Eratostene "espandibile". Partendo dal vettore
A livello logico la parte più complicata è stata, nelle "espansioni" successive alla prima, l'individuazione del primo multiplo da eliminare in relazione al generico numero primo considerato. Faccio un esempio per chiarire quello che intendo... questa è la situazione di
Ecco il codice e l'output relativo ai valori inseriti:
Prima di complicare le cose con i
Al momento ho impostato
Infine volevo qualche parere e/o consiglio sull'idea di base e su come l'ho implementata. Secondo voi è un buon approccio per una funzione next_prime per input molto grandi? O conviene utilizzare una funzione che verifica la primalità di un singolo numero alla volta?
next_prime_number(n) in C++.Per la precisione ho provato ad implementare una sorta di crivello di Eratostene "espandibile". Partendo dal vettore
v = {2,3} aggiungo N valori dispari, applico il crivello partendo dal 3 (visto che numeri pari non ce ne sono) e aggiorno v in modo che contenga solo numeri primi. Per trovare il numero primo immediatamente successivo ad n , applico la suddetta procedura fin quando l'ultimo elemento di v non è maggiore di n . A questo punto cerco il valore voluto all'interno di v dimezzando di volta in volta l'intervallo di ricerca.A livello logico la parte più complicata è stata, nelle "espansioni" successive alla prima, l'individuazione del primo multiplo da eliminare in relazione al generico numero primo considerato. Faccio un esempio per chiarire quello che intendo... questa è la situazione di
v dopo la seconda espansione, ma prima della seconda crivellatura:I numeri in rosso sono i numeri primi trovati dopo la prima crivellatura, mentre gli altri sono quelli da sottoporre alla seconda crivellatura. La difficoltà di cui parlavo è consistita nel trovare un modo efficiente per individuare l'indice relativo al primo multiplo da eliminare per il generico numero primo considerato. Per esempio considerando il
7, da dove parto? E considerando il 13 o il 17? A tal proposito, se trovate un modo più efficiente di quello che ho implementato, sono tutto orecchi.Ecco il codice e l'output relativo ai valori inseriti:
C++:
#include <iostream>
#include <cstdint>
#include <vector>
using namespace std;
void espandi_e_applica_crivello(vector<uint64_t> &v, uint64_t &last, const uint64_t N)
{
uint64_t m = v.size();
uint64_t first = last + 2;
v.reserve(m + N);
for(uint64_t i = 0; i < N; v.push_back(last += 2), ++i);
for(uint64_t i = 1, n, q, k; ; ++i)
{
if(n = v[i])
{
if((q = n * n) > last)
{
break;
}
if(q < first)
{
uint64_t r = first % n;
k = r ? (r % 2 ? (n - r) / 2 : n - r / 2) : 0;
}
else
{
k = (q - first) / 2;
}
for(uint64_t j = m + k; j < v.size(); v[j] = 0, j += n);
}
}
for(uint64_t i = m; i < v.size(); ++i)
{
if(v[i])
{
v[m++] = v[i];
}
}
v.resize(m);
}
uint64_t next_prime_number(const uint64_t n)
{
static vector<uint64_t> v = {2, 3};
static uint64_t last = v.back();
static const uint64_t N = 1'000'000;
while(v.back() <= n)
{
espandi_e_applica_crivello(v, last, N);
}
cout << "\n" << v.size() << " NUMERI PRIMI <= " << last << " (" << (double)v.size() / last * 100 << "%)\n";
uint64_t i_dx = v.size() - 1;
for(uint64_t i_sx = 0, i; i_dx != i_sx + 1; (n < v[i = (i_sx + i_dx) / 2] ? i_dx : i_sx) = i);
return v[i_dx];
}
int main()
{
uint64_t n = 47'306'346;
uint64_t p = next_prime_number(n);
cout << "\nNEXT PRIME(" << n << ") = " << p << endl;
}
Codice:
2888144 NUMERI PRIMI <= 48000003 (6.01697%)
NEXT PRIME(47306346) = 47306351
Process returned 0 (0x0) execution time : 1.698 s
Press any key to continue.Prima di complicare le cose con i
big_int , ho preferito limitarmi all'utilizzo degli uint64_t . Al momento ho impostato
N = 1.000.000 , consigli su come settare tale variabile al fine di ottimizzare le prestazioni?Infine volevo qualche parere e/o consiglio sull'idea di base e su come l'ho implementata. Secondo voi è un buon approccio per una funzione next_prime per input molto grandi? O conviene utilizzare una funzione che verifica la primalità di un singolo numero alla volta?
).
invece di fare la divisione per 2 fai uno shift verso destra di un bit con riempimento di zeri a sinistra (aumenta l'efficienza: spostare verso destra di un bit un intero equivale a dividerlo per 2 ma si fa in meno tempo macchina rispetto alla divisione)
).