Soyez le premier à donner votre avis sur cette source.
Vue 2 299 fois - Téléchargée 165 fois
// calculate the sieve isPrime from isPrime[0] to isPrime[N] void SieveRecur(uint N, bool *isPrime) { // len(isPrime) > N // avant le premier appel, isPrime[0..N] doit être initialisé à true if (N <= 3) {isPrime[0] = isPrime[1] = false; return;} uint R = sqrt(N); SieveRecur(R, isPrime); for (uint m, p = 2; p <= R; ++p) if (isPrime[p]) { // p is prime { for (m = p*p; m <= N-p; m += p) isPrime[m] = false; isPrime[m] = false; } } void Sieve0(uint N, bool *isPrime) { // len(isPrime) > N isPrime[0] = isPrime[1] = false; memset(isPrime+2, true, N-1); uint R = sqrt(N); for (uint p=2; p <= R; ++p) if (isPrime[p]) for (uint q = p, Q = N/p; q <= Q; ++q) isPrime[p*q] = false; } // bool *EratoD(uint N, bool *isPrime) { isPrime[0]=false; isPrime[1]=false; memset(isPrime+2,true,N-1); for (uint p=2; p*p<=N; ++p) if (isPrime[p]) for (uint q=N/p; q>=p; --q) if (isPrime[q]) isPrime[p*q]=false; return isPrime; }Malheureusement, la fonction SieveRecur est à peine plus rapide que Sieve0 décrite dans mes articles précédents:
SieveRecur: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 2 ms N = 10000000, n = 664579, t = 92 ms N = 100000000, n = 5761455, t = 1270 ms N = 1000000000, n = 50847534, t = 15607 ms Sieve0: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 3 ms N = 10000000, n = 664579, t = 100 ms N = 100000000, n = 5761455, t = 1347 ms N = 1000000000, n = 50847534, t = 16263 ms EratoD: N = 10, n = 4, t = 0 ms N = 100, n = 25, t = 0 ms N = 1000, n = 168, t = 0 ms N = 10000, n = 1229, t = 0 ms N = 100000, n = 9592, t = 0 ms N = 1000000, n = 78498, t = 3 ms N = 10000000, n = 664579, t = 39 ms N = 100000000, n = 5761455, t = 422 ms N = 1000000000, n = 50847534, t = 4868 msCe qui est déjà "pas si mal" !
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.