Problem 1: Coprimes

Points:

Small Case: 10 Answer: 1232

Large Case: 20 Answer: 4027392

A function ,f(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n (i.e. having no common positive factors other than 1).

For example, f(9)=6 since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9.

Find the value of f(n) for

Small Case: n=2468

Large Case: n=12345678

Solution:

f(n) is euler totient function.

f(n) is given by

where p are prime factors of n.

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<map>

#include<cmath>

#define ll long long int

#define MAX 255800ll

using namespace std;

bool ar[MAX]={0};

ll pr[MAX]={0},len=0;

ll func(ll n)

{

		ll ans=n;

        ll y=(ll)sqrt(n+1);

        for(ll i=0,x=0;pr[i]<=y && i<len && pr[i]<=n;i++)

        {

            if(n%pr[i]==0)

            {

                x=pr[i];

                ans=(ans*(x-1))/x;

                while(n%x==0)

                    n/=x;

            }

        }

        if(n>1)

            ans=(ans*(n-1))/n;

        //printf("%lld\n",ans);

		return ans;

}

int main()

{

    ll i,j,n,ans=0,y;

    for(i=2;i<=MAX;i++)

        if(ar[i]==0)

        {

            pr[len++]=i;

            for(j=i<<1;j<=MAX;j+=i)

                ar[j]=1;

        }

    scanf("%lld",&n);

    ans=func(n);

    printf("%lld\n",ans);

    return 0;

}