UVA - 10179 - Irreducable Basic Function

Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1120

Explanation: Just use Euler's Phi function, also known as the totient function, is a function that, for a given positive integer , calculates the number of positive integers smaller than or equal to  that are relatively prime to . (Note that except when , only integers strictly smaller than  are counted, because .)

Code First Then See Solution


Code: 

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll phi(ll n)
{
    ll res=n;
    if(res%2==0)
    {
        while(res%2==0)
        {
            res/=2;
        }
        n-=n/2;
    }
    for(ll i=3;i*i<=res;i+=2)
    {
        if(res%i==0)
        {
            while(res%i==0)
                res/=i;
            n-=n/i;
        }
    }
    if(res>1)
        n-=n/res;
    return n;
}


int main()
{
   long long n;
   while(cin>>n)
   {
       if(n==0)
        break;
       ll ans=phi(n);
       cout<<ans<<endl;
   }
   return 0;
}

UVA - 10394 - Twin Primes

Problem link: https://onlinejudge.org/external/103/10394.pdf

Explanation: Precalculate all twin primes.




Code First Then See Solution 


Code: 

#include <bits/stdc++.h>

#define mx 20000009
#define ll long long

using namespace std;

long long int a[mx],b[mx];

int main()
{

    for(ll i=0;i<mx;i++)
        a[i]=0;
    a[0]=a[1]=1;
    for(ll i=4;i<mx;i+=2)
        a[i]=1;
    for(ll i=3;i<sqrt(mx);i+=2)
    {
        if(a[i]==0)
        {
            for(ll j=i*i;j<mx;j+=i)
                a[j]=1;
        }
    }
    ll k=1;
    for(ll i=2;i<mx;i++)
    {
        if(a[i]==0&&a[i+2]==0)
            b[k++]=i;
    }
    ll s;
    while(cin>>s)
    {
        cout<<"("<<b[s]<<", "<<b[s]+2<<")"<<endl;
    }
    return 0;
}