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.
- ¿Cuáles son los requisitos matemáticos para comenzar a estudiar el programa Langlands?
- ¿Cuál es el dígito unitario de 3 ^ 460?
- ¿Hay algún orden en el que aprenda sobre las maravillas de la teoría de números?
- ¿Cómo se relacionan la suma de números y la unión de conjuntos?
- ¿Cuál es una explicación intuitiva del tamiz Selberg?
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