also tc page tat arun said says as follows...
1. If *p* is prime, then φ (*p*) = *p* - 1 and φ (*pa*) = *p** a* * (1 -
1/*p*) for any *a*.
2. If *m* and *n* are coprime, then φ (*m* * *n*) = φ (*m*) * φ (*n*).
3. If *n* = , then Euler function can be found using formula:
φ (*n*) = *n* * (1 - 1/*p* 1) * (1 - 1/*p* 2) * ... * (1 - 1/*p k*)
make sure u check this...
i did the loop stuff in that page.. ve not tried ma hands on sieve...
On Sun, Jun 5, 2011 at 9:20 PM, kartik sachan <kartik.sac...@gmail.com>wrote:
> @keyan then also it is given time limit exceed ................
> i don't know what to do..............plzz help me plzzzzzzzzzzzzz
>
> my modified code is :
>
> # include<stdio.h>
> int main()
> {
> long long int phi[1000001];
> long long int i,j,t1,k;
> scanf("%lld",&t1);
> while(t1--)
> {
> scanf("%lld",&k);
> phi[1]=1;
> for ( i=2; i<=k; ++i) phi[i]=i;
> for ( i=2; i<=k; ++i)
>
> if (phi[i]==i) // prime
> for ( j=i; j<=k; j+=i)
>
> phi[j]=phi[j]/i*(i-1);
>
>
>
>
> printf("%lld\n",phi[k]);
> }
> return 0;
>
> }
>
>
>
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
