rahulpadhy's blog

Euler-Totient
By rahulpadhy, history, 9 years ago, In English

I am trying to find out the euler-totient values for all integers upto 10 ^ 5. However, I am getting terrible outputs for the below code, Can anyone please suggest me as to where am I going wrong ? Thanks in advance. :) Here's the link to my code. http://codepad.org/hexai2nk

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

In line 20, you need to increment j in steps of i.

(Man, the number of times I made that mistake myself...)

Also, if you want spf[j] to be the smallest prime factor of j, line 23 should be spf[j] = min(spf[j],i).

Also, using the pow function on integers is almost never a good idea, as it uses doubles.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

your code is a little messy and i wasn't able to understand it very well anyway... Euler’s Totient function Φ(n) for n is the count of numbers in {1, 2, 3..., n} that are prime to n... but instead of implementing exactly what was written above we can find Euler's product. Euler’s product formula for totient functions is equal to the product over all prime factors p of n. for ex: Φ(4)=4 * (1-1/2) =2. Φ(6)=6 * (1-1/2) * (1 – 1/3) =2. here is the code http://pastebin.com/AZZW7JS7 hope that I helped :D

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.net/blog/entry/17881#comment-227475

→ Reply