+ 7

# [ASSIGNMENT] Eulers totient

Phi(n) - also known as totient(n) - is the number of integer lower than n such that k and n have no common divisor (ie gcd(n,k)==1) Code a function phi(n). Note that if gcd(a,b)=1 then phi(ab)=phi(a)phi(b) Test values: p in [13,17,2593] => phi(p)=p-1 2=>1 16=>8 100=>40 25=>20 33=>20 4=>2 More on Totient: http://mathworld.wolfram.com/TotientFunction.html

29 Answers

+ 18

https://code.sololearn.com/co96oapIC0Iq/?ref=app

+ 18

Accelerated using prime factorization:
https://code.sololearn.com/cgKQ250c4ibF/?ref=app

+ 15

Nevfy
Ok, I got it 👍

+ 14

Nevfy
I have no problem with speed, but I have a problem with memory limit on SL 😁
On my Intellij IDE, the time for range 1-180.000 is 4.297 second.
Here's :
https://code.sololearn.com/c9xS6mscs7W7/?ref=app
I try to write a solution using the SieveOfEratosthenes method to avoid memory limit exceed.

+ 12

VcC
I made some changes to ver.2: I changed the type of int to type long, inserted line 26 to break loop when N=1
Now works for N over 9000000000000000000 (single check)

+ 11

VcC Nevfy
I'm not a mathematician, and I do not know if my second version has some name for algorithm...but it seems to me it works as it should.
I used prime factorization of N.
For all distinct factors I used the function phi (p) = p-1
For repeating factors: (p) = p or p-0
For example :
N=220
factors=(11,5,2,2)
distinct=(11,5,2)
repeated=(2)
phi(11)*phi(5)*phi(2)*2 = 80
For example :
N=50.000
factors =(5,5,5,5,5,2,2,2,2)
distinct =(5, 2)
repeated=(5,5,5,5,2,2,2)
phi(5)*phi(2)*5*5*5*5*2*2*2=20.0000

+ 11

VcC
Thank you 😉

+ 11

Nevfy
Okay. I try to modify the code for numbers in the range during the day. But on SL, the problem occurs when printing a large number of lines or characters - shows the time limit exceed. Is there a way to solve this problem?

+ 10

Nevfy
That's true.
With gcd(k, n) my code works for N<100.000 without limit exceed.
With prime factorization and phi(p^n) works for N over 500 milion

+ 10

Nevfy
Yes, single check.

+ 8

Without imports:
https://code.sololearn.com/cX1DKYARwlgg/?ref=app

+ 4

This an oneliner, which use a naive approach:
https://code.sololearn.com/c8DFh5a7O29G/?ref=app
@VcC Could you also add some input-output examples to simplify examination of the codes?

+ 3

Ok, finally I decided to convert my optimization idea to a code. Here it is:
https://code.sololearn.com/c8O6H0iKshMM/?ref=app
I have found that optimized version works three times quicker checking consequently all numbers from 1 to 2000. You can type only the highest limit using my code and see the comparison (for sure it doesn't work for big limits due to Time Limit of SoloLearn).

+ 2

Any language

+ 2

phi(p^n)=p^n-p^n-1 if p is prime
The problem in your version is that factorization can be very slow for large primes. You could eliminate 2, then limit the loop to odd numbers and up to sqrt(n) only

+ 2

@VcC That's a great formula! Now optimized version will work even quicker!
@LukArToDo And it also means that your code is correct.

+ 2

@LukArToDo Just do not print them :-)
Time spent for the calculations for all numbers from 1 to given by user limit is the only required line in the output. Is there any timing library in kt?

+ 1

Any specific language it needs to be done in?

+ 1

@LukArToDo
Your first code: phi(25) = phi(5)*phi(5) = 20
The answer 20 is correct but the output is wrong. First of all gcd(5,5) != 1, so this formula can't be used, secondly, phi(5) = 4.

+ 1

@VcC The only thing to speed up the code, which comes to my mind is:
1. Check if number is Prime?
- if so return n-1
- if not, we just lost some time
Complexity O(sqrt(n)) for direct check or O(log(n)) for a probabilistic one.
2. Do a prime factorization of number.
2.a. Create list of Primes from 2 to n//2.
As always I offer a Sieve algorithm with complexity of O(n*log(log(n))).
2.b. Factorization itself has a complexity of about O(log(n))
3. Use formula phi(ab)=phi(a)*phi(b) if gcd(a,b)=1.
It means that for all Primes, which are met only once, we can use phi(a)=a-1
For others - do a direct calculation.
Example: 725
1. It is not Prime.
2. 725 = 5^2 * 29
3. phi(725) = phi(25) * 28
I'm not sure about complexity of GCD algorithm, but let's say O(log(n)), where n is the biggest from 2 input number.
So direct check has a complexity of about O(n*log(n)).
It is a bit difficult to estimate the complexity of proposed above optimization, but I think that it is about the same. What do you think? Do you also have some other ideas?
If you offer a good test set to check the performance of both algorithm, I can code my idea and we can check it...