Salut à tous.
Le but est de partir d'un nombre très très grand qui est le résultat d'une multiplication de deux nombres premiers (N = a * b).
Bien sûr, essayer de retrouver ces deux nombres premiers le plus rapidement.
Je me suis penché sur cette question, et la première idée consiste à décomposer ce nombre N sous la forme : x * ( x + y ).
Ce qui revient à dire que x est la racine carré du nombre N et ce x est en fait a.
Je dois retrouver b qui est en fait le reste de : N - x*x où x est initialisé à la racine carré de N puis varie par décrémentation.
Le mieux est de donner mon petit programme en 'C' :
Et voici quelques résultats :
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
43
44
45
46
47
48
49 /**********************************************/ /* */ /* Décomposition de la multiplication */ /* */ /**********************************************/ #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <math.h> /********************************/ /* */ /* Procédure Principale */ /* */ /********************************/ int main(void) { unsigned long long int a,b,i,n; /*==========================*/ /* Saisie du nombre */ /*==========================*/ printf("Maximum : %llu\n", ULLONG_MAX); printf( "Veuillez saisir le nombre à décomposer : " ); scanf( "%llu", &n ); /*=====================*/ /* Préparation */ /*=====================*/ a = (long long int)sqrt(n); b = n - a*a; i = 2 * a + 1; /*================*/ /* Calcul */ /*================*/ while ((b%a) != 0) { b += (i -= 2); a--; } printf("\nA = %8.0llu B = %8.0llu Res = %llu\n", a, (a + (b/a)), (a*a + b)); }
Ou encore :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 Maximum : 18446744073709551615 Veuillez saisir le nombre à décomposer : 1234567890987654321 A = 1111011111 B = 1111211111 Res = 1234567890987654321 Appuyez sur une touche pour continuer...
Le résultat est assez rapide quand la multiplication est proche de son carré.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 Maximum : 18446744073709551615 Veuillez saisir le nombre à décomposer : 987654313456789 A = 203423 B = 4855175243 Res = 987654313456789 Appuyez sur une touche pour continuer...
Question : peut-on améliorer cet algorithme ?
@+
Partager