Crible d'Atkin

Version imprimable

25/02/2008, 15h26
piotrr

Crible d'Atkin

Comment trouver tous les couples solutions et de manière optimisée des équations du genre:

4x² + y² = n

ou encore

3x² - y² = n

merci
25/02/2008, 16h28
millie

x et y sont entiers ?
25/02/2008, 16h59
Zavonen

et n?
26/02/2008, 08h53
piotrr

Oui oui.
On connait n entier positif et on cherche le couple x, y d'inconnues entières et positives aussi.
26/02/2008, 10h39
Zavonen

Alors force brute.
On a une borne supérieure pour abs(y) soit sqrt(n)
On a une borne supérieure pour abs(x) soit sqrt(n/4)
On teste tous les couples (x,y) dans le rectangle
On ne garde que les bons.
26/02/2008, 12h38
piotrr

Citation:

Envoyé par Zavonen

Alors force brute.
On a une borne supérieure pour abs(y) soit sqrt(n)
On a une borne supérieure pour abs(x) soit sqrt(n/4)
On teste tous les couples (x,y) dans le rectangle
On ne garde que les bons.

Ok mais pour 3x² - y² = n par exemple, ça ne marche pas. N'as - t - ton pas une infinité de solutions dans ce cas ci?

merci
26/02/2008, 12h53
Zavonen

Je n'avais pas vu le second exemple.
Dans le premier cas on a un ensemble borné (ellipse) on peut donc faire comme je suggère.
Dans le second exemple, l'ensemble est non borné (hyperbole) ça ne marche plus.
Si au lieu de 3 on avait 4, on pourrait factoriser et partir des décompositions de n en produit de 2 facteurs. Mais avec 3 ...
26/02/2008, 12h56
piotrr

Oui c'est bien là le problème....
C'est un algorithme qui demande ça:

http://fr.wikipedia.org/wiki/Crible_d%27Atkin

Je pense qu'il y a une erreur dans l'algo.
26/02/2008, 15h27
Jedai

Je pense que c'est les solutions pour x et y inférieures à la limite du crible.

--
Jedaï
26/02/2008, 15h42
pseudocode

Citation:

Envoyé par Jedai

Je pense que c'est les solutions pour x et y inférieures à la limite du crible.

Je confirme cette assertion. :aie:
27/02/2008, 12h52
piotrr

Je ne pense pas.

Par exemple pour 383 : il est premier et il appartient à la troisième liste, celle pour laquelle on cherche les couples de la forme 3x² - y² = n .

Si on prend pour valeur limite 400 alors on trouve pour x et y:

12 et 7
17 et 22
31 et 50
56 et 95
112 et 193
207 et 358

soit 6 couples solutions
donc un nombre paire de couples solutions
donc le nombre est évincé de la liste
autrement dit il n'est pas considéré comme premier ...

merci
27/02/2008, 14h31
pseudocode

Citation:

Envoyé par piotrr

Par exemple pour 383 : il est premier et il appartient à la troisième liste, celle pour laquelle on cherche les couples de la forme 3x² - y² = n .
(...)
autrement dit il n'est pas considéré comme premier ...

L'erreur classique.

Dans la 3eme liste, il faut que X>Y
27/02/2008, 14h59
piotrr

Citation:

Envoyé par pseudocode

L'erreur classique.

Dans la 3eme liste, il faut que X>Y

Merci beaucoup!

D'après ce que j'ai déjà testé ça doit être ça!

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

Citation:

Envoyé par piotrr

Merci beaucoup!

D'après ce que j'ai déjà testé ça doit être ça!

sans blagues ? :P

Citation:

Est ce que tu as déjà programmé le crible d'Atkin

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Atkin {
 
	public static void main(String[] args) {
 
		// Upper bound of prime list to generate
		int MAX=1000;
 
		// initialize the array to false (by default in java)
		boolean[] isprime = new boolean[MAX];
 
		// Atkin's sieve (binary quadratic)
		int n=0,x2=0,y2=0,mod=0;
		for(int x=1;x<=MAX;x++) {
			x2=x*x; 
			for(int y=1;y<=MAX;y++) {
				y2=y*y;
 
				n = 4*x2+y2;
				if ( n<MAX ) {
					mod = n%60;
					if (mod==1 || mod==13 || mod==17 || mod==29 || mod==37 || mod==41 || mod==49 || mod==53) isprime[n]=!isprime[n];
				}
 
				n = 3*x2+y2;
				if ( n<MAX ) {
					mod = n%60;
					if (mod==7 || mod==19 || mod==31 || mod==43) isprime[n]=!isprime[n];
				}
 
				if ( x>y ) {
					n = 3*x2-y2;
					if ( n<MAX ) {
						mod = n%60;
						if (mod==11 || mod==23 || mod==47 || mod==59) isprime[n]=!isprime[n];
					}
				}
			}
		}
 
		// remove multiples of prime^2
		for(int i=0;i<MAX;i++) {
			if (isprime[i]) {
				int i2 = i*i;
				for(int j=i2;j<MAX;j+=i2) isprime[j]=false;
			}
		}
 
		// force the 60 first prime numbers
		for(int i:new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59})
			isprime[i]=true;
 
		// print primes
		for(int i=0;i<MAX;i++)  
			if (isprime[i]) System.out.println(i);
	}
 
}

Citation:

, si oui est - il vraiment plus performant que celui d'Erastosthene? J'ai du mal à le croire....

Si on optimise le code, oui, il est plus rapide. Et surtout il est parallelisable (un ordinateur dédié pour chacune des 3 listes)

27/02/2008, 15h25
piotrr

et pour 539 ...

Il fait aussi parti de la troisème liste.

Mais je trouve comme unique couple solution:

14 et 7

donc le compte de couples solutions est impaire donc on garde le nombre...

Seulement 539 n'est pas premier !

Comment est ce possible?

merci
27/02/2008, 15h53
pseudocode

Citation:

Envoyé par piotrr

et pour 539 ...

Il fait aussi parti de la troisème liste.

Mais je trouve comme unique couple solution:

14 et 7

donc le compte de couples solutions est impaire donc on garde le nombre...

Seulement 539 n'est pas premier !

Comment est ce possible?

merci

Sans doute parceque ca marche mieux quand on déroule complètement l'algorithme, en particulier la partie finale ou on supprime les multiples des p^2.

Car 539 = 11 * 7^2
27/02/2008, 18h22
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.
27/02/2008, 18h39
pseudocode

On peut même lire le PDF original qui contient le pseudocode (page 3):

Prime sieves using binary quadratic forms (Atkin, Bernstein)
27/02/2008, 20h13
piotrr

Citation:

Envoyé par pseudocode

On peut même lire le PDF original qui contient le pseudocode (page 3):

Prime sieves using binary quadratic forms (Atkin, Bernstein)

Merci mais ils me demandent un mot de passe...
27/02/2008, 20h15
pseudocode

Citation:

Envoyé par piotrr

Merci mais ils me demandent un mot de passe...

8O ??

L'AMS demande des mots de passe maintenant ?
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)