¿Cómo encuentro todos los pares de enteros cuyo producto es menor que igual a un número particular?

Digamos que queremos encontrar todos los pares [matemática] P = (x, y) [/ matemática] donde la [matemática] x * y \ leq N [/ matemática].

Lo que haría es comenzar desde [matemáticas] x = 2 [/ matemáticas], y continuar hasta [matemáticas] \ frac {N} {2} [/ matemáticas] y para cada x, contaría pares hasta [matemáticas] N [/ math] donde [math] x * y \ leq N [/ math].

  int cuenta = 1;
 vector <par > pares;
 pares.push_back (1, N);
 para (int x = 2; x <= N / 2; x ++)
 {
     para (int y = 2; x * y <= N; y ++)
     {
         pares.push_back (make_pair (x, y));
         recuento ++;
     }
 }

Obviamente, esto es una [matemática] O (n ^ 2) [/ matemática] y estos pares no están ordenados. [math] (x, y) [/ math] y [math] (y, x) [/ math] se tratan de la misma manera.

Si los enteros negativos también están cubiertos, entonces cada par se insertaría nuevamente, siendo ambos números negativos.

Si solo desea contar el número de pares enteros con un producto menor o igual que [math] N [/ math].

Supongo que seguir la aproximación funcionaría. [1]

Si [math] xy \ leq N \ implica y = \ left \ lfloor \ frac {N} {x} \ right \ rfloor [/ math],

Si calculamos la suma de [matemáticas] x \ rightarrow 1 … N [/ matemáticas]. Contaría todos los pares, pero se ordenarán pares [math] (x, y) [/ math] se contarían dos veces, pero todos los pares donde [math] x [/ math] e y son iguales se contarían como [ matemáticas] 1 [/ matemáticas].

Para agregar el número donde [matemática] x = y [/ matemática] nuevamente, agregamos el número de pares [matemática] (x, x) [/ matemática] donde [matemática] x ^ 2 \ leq N [/ matemática] que es [math] \ sqrt {N} [/ math]. Ahora que todos los pares se cuentan dos veces, dividimos entre [matemáticas] 2 [/ matemáticas].

[matemáticas] Count (n) = \ frac {1} {2} \ left (\ left \ lfloor \ sqrt {N} \ right \ rfloor + \ sum_ {k = 1} ^ {N} \ left \ lfloor \ frac { N} k \ right \ rfloor \ right) [/ math]

Espero que eso ayude.

Feliz codificación

Notas al pie

[1] número de soluciones de x * y