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' :
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));
}
Et voici quelques résultats :
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...
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 : 987654313456789
 
A =   203423   B = 4855175243   Res = 987654313456789
Appuyez sur une touche pour continuer...
Le résultat est assez rapide quand la multiplication est proche de son carré.

Question : peut-on améliorer cet algorithme ?

@+