Crible d'Atkin

Version imprimable

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

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 ?

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