Crible d'Atkin

Version imprimable

Voir 40 message(s) de cette discussion en une page

27/02/2008, 20h35
millie

Citation:

Envoyé par pseudocode

8O ??

L'AMS demande des mots de passe maintenant ?

Oui quand on clique directement, ça demande un mot de pass. Mais si on fait clic droit enregistrez sous, ça marche..... (...) (......)
27/02/2008, 20h51
piotrr

Citation:

Envoyé par Zavonen

Le wiki français sur le crible d'Atkin est parfaitement incompréhensible.
Par contre la version anglaise est limpide:
http://en.wikipedia.org/wiki/Sieve_of_Atkin
L'algo donné est parfaitement clair et traduisible immédiatement en n'importe quel langage.

J'ai plutôt l'impression que soit il est incomplet, soit il est complètement faux soit il propose toute autre vision du crible (pas du tout optimisée pour avoir essayer de l'implémenter...).

Je pense donc complètement mettre de côté la version française pour me concentrer sur l'anglaise...

Qu'en pensez vous?

merci
27/02/2008, 21h13
pseudocode

Citation:

Envoyé par piotrr

Je pense donc complètement mettre de côté la version française pour me concentrer sur l'anglaise...

Qu'en pensez vous?

Le pseudo-code de la version anglaise est déjà une version optimisée (modulo 12 au lieu de 60). Sinon tu peux prendre mon code Java qui est une implémentation du PDF (pas du tout optimisée par contre).
27/02/2008, 21h34
Zavonen

Je viens d'implémenter le pseudo-code de la version anglaise mot pour mot en python, ça passe !
27/02/2008, 21h56
piotrr

Citation:

Envoyé par Zavonen

Je viens d'implémenter le pseudo-code de la version anglaise mot pour mot en python, ça passe !

ça m'interesse grandement!

serait - ce possible d'y jeter un coup d'oeil ?

merci

Citation:

Envoyé par Zavonen

Je viens d'implémenter le pseudo-code de la version anglaise mot pour mot en python, ça passe !

ils sont forts ces anglais.

Sinon j'ai une version plus optimisée (moins de tours de boucles en séparant le calcul des 3 listes et en calculant les bornes au plus juste):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
// Upper bound of prime list to generate
int MAX=10000;
 
// initialize the array to false (by default in java)
boolean[] isprime = new boolean[MAX];
 
// sieve 1: 4x²+y²
for(int x=1,x2=1;(4*x2)<MAX;x++,x2=x*x)
	for(int y=0,n=0,mod=0; n<MAX; y++,n=4*x2+y*y,mod=n%12)
		if (mod==1 || mod==5) isprime[n]=!isprime[n];
 
// sieve 2: 3x²+y²
for(int x=1,x2=1;(3*x2)<MAX;x++,x2=x*x)
	for(int y=0,n=0,mod=0; n<MAX; y++,n=3*x2+y*y,mod=n%12)
		if (mod==7) isprime[n]=!isprime[n];
 
// sieve 3: 3x²-y²
for(int x=1,x2=1;(2*x2)<MAX;x++,x2=x*x)
	for(int y=x,n=0,mod=0;y>0 && n<MAX;y--,n=3*x2-y*y,mod=n%12)
		if (mod==11) isprime[n]=!isprime[n];
 
// remove multiples of prime^2
for(int i=5,i2=i*i;i2<MAX;i++,i2=i*i)
	if (isprime[i])
		for(int j=i2;j<MAX;j+=i2) isprime[j]=false;
 
// force the 2 first prime numbers
isprime[2]=true;
isprime[3]=true;
 
// print primes
for(int i=0,n=0;i<MAX;i++)  
	if (isprime[i]) System.out.println((++n)+": "+i);

bon, j'avoue, c'est moins lisible. :aie::aie:

Citation:

serait - ce possible d'y jeter un coup d'oeil ?

Voilà:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import math
 
limite=1000
crible=[0]*limite
racine= math.sqrt(limite)+1
 
def cond1 (n):
    return n<limite and ((n%12==1)or(n%12==5))
def cond2(n):
    return n<limite and (n%12==7)
def cond3(x,y,n):
    x>y and (n<limite)and (n%12==11)
def debut():
    for x in range(1,racine):
        for y in range (1,racine):
            n=4*x*x+y*y
            if cond1(n):
                crible[n]=not crible[n]
            n=3*x*x+y*y
            if cond2(n):
                crible[n]=not crible[n]
            n=3*x*x-y*y
            if cond3(x,y,n):
                crible[n]= not crible[n]
def fin():
    for n in range(5,limite):
        L=[k*n*n for k in range(1,limite/(n*n))]
        for k in L:
            crible[k]=0
 
def affiche():
    for i in range(5,limite):
        if crible[i]:
            print i
 
def main():
    debut()
    fin()
    affiche()
 
if __name__ == '__main__':
    main()

28/02/2008, 09h57
piotrr

Merci beaucoup!
Je l'avais aussi implenté (en java) mais j'avais fait une toute petite erreur de traduction qui ne donne pas du tout le résultat voulu...

Pour conclure, êtes - vous bien d'accord avec moi que l'algorithme sur wikipedia en français est juste à priori mais très dur à interpréter?

merci
28/02/2008, 10h04
pseudocode

Citation:

Envoyé par piotrr

Pour conclure, êtes - vous bien d'accord avec moi que l'algorithme sur wikipedia en français est juste à priori mais très dur à interpréter?

non, il est faux. Il manque le "x>y" dans la construction de la liste 3. :?
05/09/2012, 20h28
dev-contrib

Citation:

Envoyé par piotrr

Est ce que tu as déjà programmé le crible d'Atkin, si oui est - il vraiment plus performant que celui d'Erastosthene? J'ai du mal à le croire....

merci encore

Si tu veux y a ce site qui peu t'aider.
http://compoasso.free.fr/primelistwe...me/accueil.php

Il y a plusieurs implémentations d'Atkin et d'Erastosthene en java (optimisées ou non)

Voir 40 message(s) de cette discussion en une page