Crible d'Atkin

**piotrr** · 25/02/2008, 15h26

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

**millie** · 25/02/2008, 16h28

x et y sont entiers ?

**Zavonen** · 25/02/2008, 16h59

et n?

**piotrr** · 26/02/2008, 08h53

Oui oui.
On connait n entier positif et on cherche le couple x, y d'inconnues entières et positives aussi.

**Zavonen** · 26/02/2008, 10h39

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.

**piotrr** · 26/02/2008, 12h38

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

**Zavonen** · 26/02/2008, 12h53

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

**piotrr** · 26/02/2008, 12h56

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.

**Jedai** · 26/02/2008, 15h27

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

--
Jedaï

**pseudocode** · 26/02/2008, 15h42

Envoyé par Jedai

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

Je confirme cette assertion.

**piotrr** · 27/02/2008, 12h52

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

**pseudocode** · 27/02/2008, 14h31

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

**piotrr** · 27/02/2008, 14h59

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

**pseudocode** · 27/02/2008, 15h11

Envoyé par piotrr

Merci beaucoup!

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

sans blagues ?

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

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
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);
	}
 
}

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

**piotrr** · 27/02/2008, 15h25

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

**pseudocode** · 27/02/2008, 15h53

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

**Zavonen** · 27/02/2008, 18h22

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.