Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Función φ de Euler»
Contenido eliminado Contenido añadido
+página, trasladado de eswiki https://es.wikipedia.org/w/index.php?title=Funci%C3%B3n_%CF%86_de_Euler&oldid=86112906 bajo licencia GFDL y CC SA BY 3.0 |
+contenido |
||
Línea 16:
donde los ''p'' son los distintos primos que dividen a ''n''.
== Descripción formal ==
=== Versión iterativa ===
De la definición general,
:<math>\varphi(n) := \sum_{{1 \leq k \leq n}\atop {\operatorname{mcd}(k,n)=1}} 1 </math>
y tomando por convenio que φ(0)=1, se obtiene la versión [[Iteración|iterativa]].
'''función''' <math>\varphi(n)\,</math>
'''devolver''' <math>1</math> '''si''' <math>n=0\,</math>
<math>j \leftarrow 0</math>
'''para''' <math>k \in 1..n</math> '''hacer'''
<math>j \leftarrow j+1</math> '''si''' <math>\operatorname{mcd}(n,k)=1</math>
'''devolver''' <math>j</math>
Esta versión tiene fácil implementación en una computadora, pero no es eficiente para valores grandes de ''n'':
=== Versión por factorización ===
Se basa en la definición de la función mediante el producto de Euler
:<math>\varphi(n):= n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>
y utiliza algún algoritmo de factorización eficiente de propósito general como puede ser la criba general del cuerpo de números (GNFS).
== Implementación en Matlab/Octave ==
Línea 41 ⟶ 67:
endfunction
</source>
== Referencias ==
* Octavian Cira, Florentin Smarandache, ''Solving Diophantine Equations'', Infinite Study, ISBN 1599733072, pp:64-68
| |||