[c++]numeri primi in maniera __efficente__[lungo]

[shinya]

Ciao a tutti! E' un sacco di tempo che sto dietro a questo problema, senza trovare una soluzione funzionale. C'è questo sito, del quale ho postato tempo fa, che raccoglie una serie di problemi in cui ci si può cimentare, mandando poi il programma scritto ad un "tester" che verifica che la soluzione sia corretta e stia nei limiti di tempo.
Questo è un semplice problema di ricerca di numeri primi. Il testo del problema lo potete trovare qui: http://spoj.sphere.pl/problems/PRIME1/

In pratica il programma prende una prima riga in input con il numero n dei casi da valutare e poi n righe con il range in cui calcolare i numeri primi, ad esempio:
Input:
2
1 10
50 100

Il programma deve stampare qualcosa tipo:
2
3
5
...e via di seguito.

Il range è da 1 a 1000000000, e la differenza tra max e min non può essere superiore a 100000. Ma al link di prima trovate tutto il testo del problema descritto in maniera più accurata.

Ok, veniamo alla ciccia. Questo è il miglior tentativo che mi è saltato fuori, ma che ovviamente esce dal tempo massimo:

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char **argv)
{
        unsigned long long min = 0, max = 0, n = 0;

        cin >> n;
        while (n--) {
                cin >> min;
                cin >> max;
                vector<bool> p(max+1);

                for (vector<bool>::size_type i = 0; i < p.size(); i++)
                        p[i] = true;
                p[0] = p[1] = false;

                for (vector<bool>::size_type i = 0; i*i < p.size(); i++)
                        if (true == p[i])
                                for (vector<bool>::size_type j = i+i; j < p.size(); j+=i) 
                                       p[j] = false;

                for (vector<bool>::size_type i = 0; i < p.size(); i++)
                        if (true == p[i] && i > min)
                                cout << i << endl;
        }

        return 0;
}

E' un classico crivello di Eratostene. Spero sia comprensibile. Nel caso non lo fosse ditemelo così aggiungo qualche commento.
Il collo di bottiglia qui è evidente: calcolo sempre tutti i numeri primi da 2 a max. Allora ho pensato:"bene, siccome devo calcolare al massimo i numeri primi fino a 1 miliardo, la cui radice quadrata è < 32000, è sufficiente calcolare i numeri primi fino a 32000 e usare quelli per eliminare tutti i loro multipli nel range richiesto".

Sbaglio?? Voi avreste un metodo migliore?
Il problema è che non sono riuscito ancora a trasformare in codice quest'idea...questo è uno schizzo, nel quale manca la parte in cui devo eliminare i multipli dei numeri primi trovati in precedenza. Non riesco a trovare un modo efficente di farlo

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char **argv)
{
	//trova i numeri primi < 32000
	vector<bool> p(32000);

	for (vector<bool>::size_type i = 0; i < p.size(); i++)
		p[i] = true;
	p[0] = p[1] = false;

	for (vector<bool>::size_type i = 0; i*i < p.size(); i++)
		if (p[i])
			for (vector<bool>::size_type j = i+i; j < p.size(); j+=i)
				p[j] = false;

	for (vector<bool>::size_type i = 0; i < p.size(); i++)
		if (p[i])
			cout << i << endl;

	unsigned long long min = 0, max = 0, n = 0;
	cin >> n;

	while (n--) {
		cin >> min;
		cin >> max;

		//manca codice qui!!!
	}

	return 0;
}

Qualcuno ha qualche suggerimento? Altri metodi??
Grazie e ciao!

[shinya]

up!

[NA01]

presupponendo che non ho guardato l'algortimo ( ) ti vorrei dare un paio di dritte.
la prima cosa che ho fatto è stata prendere il tuo codice e togliere tutte le chiamate a p.size() sostituendolo con una variabile che alloca all'inizo.
il tempo di esecuzione senza la stampa è passato da

real 0m6.867s
user 0m6.455s
sys 0m0.015s

a

real 0m3.819s
user 0m3.595s
sys 0m0.006s

poi ho tolto l'allocazione delle variabili all'interno del for. le ho spostate fuori e ora non dealloca/rialloca le variabili all'interno dei cicli.
mi aspettavo di guadagnare tanto invece siamo quasi a un guadagno nullo.

real 0m3.784s
user 0m3.568s
sys 0m0.005s

con le ottimizzazione attive il primo rimane un guadagno sensibile, il secondo che già era nullo scompare quasi del tutto.

a parte questi giochini sugli algoritmi di ricerca dei numeri primi c'era un bel 3d, magari qualcuno si ricorda qualcosa...


ciao!

[shinya]

Ce l'ho fatta finalmente! Il programma è passato al test.
Se a qualcuno interessa un programmino per calcolare i numeri primi fino a 1 miliardo (e non oltre) in maniera piuttosto efficente, qui c'è il sorgente in C++.

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
typedef unsigned long long bignum;

int main(int argc, char **argv)
{
  // find the first 31626 prime numbers
  // this is because sqrt(1_000_000_000) < 31626
  bignum upto = 31626;
  vector<bool> p(upto);

  for (vector<bool>::size_type i = 0; i < upto; i++)
    p[i] = true;
  p[0] = p[1] = false;

  for (vector<bool>::size_type i = 0; i*i < upto; i++)
    if (p[i])
      for (vector<bool>::size_type j = i+i; j < upto; j+=i)
        p[j] = false;
  // end of prime calculation

  // take n test case in input and compute
  // the prime numbers in the range between
  // min and max
  bignum min = 0, max = 0, n = 0;
  cin >> n;

  while (n--) {
    cin >> min; cin >> max;
    assert(max >= min);

    bignum tmp_size = max - min + 1;
    vector<bignum> tmp(tmp_size);

    // load the vector with the range
    for (vector<bignum>::size_type i = 0; i < tmp_size; i++)
      tmp[i] = min + i;

    // another sieve
    for (vector<bool>::size_type i = 0; i*i < max; i++)
      if (p[i]) {

        // find the first multiple
        vector<bignum>::size_type j = 0;

        // go to the first non-1
        while (tmp[j] == 1)
          j++;

        bignum div = tmp[j] % i;
        if (div != 0)
          j += (i - (div));

        // delete all the other multiple of i in the range
        if (tmp[j] == i) // if tmp[j] is a prime, jump to the next one
          for (vector<bignum>::size_type k = j+i; k < tmp_size; k += i)
            tmp[k] = 1;
        else
          for (vector<bignum>::size_type k = j; k < tmp_size; k += i)
            tmp[k] = 1;
      }

    for (vector<bignum>::size_type i = 0; i < tmp_size; i++)
      if (tmp[i] != 1)
        cout << tmp[i] << "\n";
  }

  return 0;
}

Scusate i commenti in inglese, è un'abitudine. Spero possa servire a qualcuno.
Esempio di utilizzo:

shell# ./prime1
1      -> casi di test
1 10  -> range di numeri

2
3
5
7

[marco.r]

del crivello se n'era parlato ampiamente qui:
http://www.hwupgrade.it/forum/showthread.php?t=824152