Gilles59 a écrit :La definition d'un couple sexy est donnée dans La Gazette n°7 page 52 :
[ ...]
Les machines qui disposent de fonctions natives pour manipuler les nombres premiers sont à l'évidence favorisées mais tout le monde peut essayer.
À vous de jouer !
Voici, une version en 159 octets pour SHARP PC-1211 qui :
- n'est pas favorisé par la présence d'une fonction ISPRIME? native ou statistique, ni d'ailleurs d'une instruction NEXTPRIME,
- n'est pas avantagé par sa vitesse de croisière qui rend chaque test de primalité fort lent.
L'idée pour gagner un peu de temps est de mémoriser les nombres premiers au fur et à mesure de leur découverte.
Mais aussi de générer un maximum de nombres premiers par ruse; à l'aide, par exemple, de l'astuce des pas de +2,+4, +2,+4,+2,+4,... ce qui permet de générer des nombres
n presque tous premiers, sauf de temps en temps les multiples de 5, 7, 11 etc...
Ce qui fait, qu'il faut tester à chaque génération si le nombre
n généré est effectivement premier. Mais qu'il suffira de tester qu'à partir des facteurs premiers
f = 5 et suivants. Comme on peut s'arrêter à la racine de
n , on limite considérablement le nombre de tests et l'on va donc créer la liste des nombres premiers plus vite que l'on ne la parcours.
Par ailleurs +2+4 fait +6, on avance donc justement d'un pas de 6 ce qui fait que pour tester un couple sexy
(x,z), il suffit en fait de se souvenir du résultat du test de primalité de
x au moment où l'on a déterminé la primalité de
z. Entre temps on aura déterminé si
y est premier ce qui servira pour le cycle suivant.
C'est à cela que servent les indicateurs
a et
b qui mémorisent les résultats du test de primalité
p des deux précédents nombres générés.
Le kilooctets de mémoire du SHARP PC-1211 est donc utilisé de la façon suivante:
Code : Tout sélectionner
Registres Variables Lignes Désignations / Commentaires
--- ------ ------------ -------------- -------------------------------------------------------------
1 A a 1: 1-2 Indicateur primalité dernier nombre généré.
2 B b 2: 2-4 Indicateur primalité avant-dernier nombre généré.
3 C c 1: 4-4 Compteur de couples sexy.
4 D s 1: 2-2 Incrément 2s=+2 ou +4 pour génération nombres pseudo-premier n
5 E n 1: 1-4 Nombre généré (pseudo-premier)
6 F f 10 à 185 1: 3-4 Indice du dernier nombre premier mémorisé dans F()
7 G p 1: 2-4 Indicateur de primalité (p=1) pour n.
8 H q=n/F(i) 3: 3-4 Rapport pour test de primalité
9 I i 2: 3-4 Indice du facteur premier pour test primalité. i varie de 10 à f
10 J=A(10)
... ... F() 1: 3-4 Tableau mémorisant les facteurs premiers 5 7 11 ... 1061
184 A(184)
On peut en théorie aller jusqu'aux couples de valeur 1061² = 1125721, mais je dois avoué que je n'ai pas eut la patience de tester.!
Le code est le suivant:
Code : Tout sélectionner
1:A=1,C=0,D=1,E=5,F=10,G=1,J=E o21
2:B=A,A=G,G=0,E=E+2D,D=1+(D=1),I=9 o35
3:I=I+1,H=E/A(I):IF H>A(I) IF H<>INT H GOTO 3 o43
4:IF H<A(I) LET G=1,F=F+(F<184),A(F)=E:IF B LET C=C+1:PRINT E-6;E;" #";C o55
5:GOTO 2 oo5
Total: 159 octets
P.S.: Pour ceux qui auraient la patience infinie de tester au-delà des
n millionnaires, la dernière ligne peut être remplacée par un test d'arrêt du style
n<1061² évitant au PC-1211 d'afficher de faux couples sexy.
Par exemple
5:IF H<1061 GOTO 2
tout en veillant à ne pas dépasser 160 octets au risque de perdre un registre et de ne plus pouvoir mémoriser 1061 !!
Mais bon, comme il faut plusieurs jours pour arriver à ces millions, cela n'a pas d'intérêt pratique.