Originally Posted by
jedoob Hi,
Can someone please tell me how to compute the Euler totient function for large values of n?
e.g n=3800.
Me I fire up Euler and type:
Code:
>load "C:\Documents and Settings\CB\My Programs\Euler23\Euler Utils\number theory.e";
>
>
>EulerTotient(3800)
1440
>
Where EulerTotient is defined as:
Code:
function EulerTotient(n)
##
## Function to calculate the Euler Totient
## function of its argument
##
## The Euler Totient function of N returns the number
## of integers coprime to N and less than N (counting 1)
##
## Abromowitz and Stegun Section 24.3.2 gives:
##
## phi(N)=N.prod[(1-1/p),p|N]
##
## that is it is N times the product over primes p which divide
## N of (1-1/p).
##
## This is used in Eulers extension to Fermat's little
## theorem:
##
## if gcd(a,n)=1, a^phi(n) = 1 (mod n).
##
## CaptainBlack 2003
##
fctrs=factor1(n); ..gives the prime factorisation of n with muliplicities
fctrs=fctrs(:,1)'; ..just keep the distinct primes
product=n*prod(1-1/fctrs);
return round(product,0) ..round to nearest integer incase or rounding errors in float calculations
endfunction;
Note the comments are longer than the code!
RonL