Discussion :

[millie]

??

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..... (...) (......)

[piotrr]

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

[pseudocode]

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).

[Zavonen]

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

[piotrr]

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

[pseudocode]

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 java :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Zavonen]

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

Voilà:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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()

[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

[pseudocode]

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.

[dev-contrib]

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)