Can sum1 plz give me the link to the problem? 2011/6/5 keyan karthi <[email protected]>
> 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 <[email protected]>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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
