Uva 10699 - Count the factors

/*

    Uva 10699 - Count the factors
    Verdict: Accepted
    Time : 0.453
*/
/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

bool stats[MX];
L vpsz,cnt;
vector <L> vp;
vector <L> facto;
void prime ()
{
    L i,j,qrt;

    for (i=4;i<=MX;i+=2)
    {
        stats[i] = true;
    }

    qrt = (long) sqrt(double(MX));

    vp.pb (2);
    for (i=3;i<=qrt;i+=2)
    {
        if (!stats[i])
        {
            for (j=i*i;j<=N;j+=i+i)
            {
                stats[j] = true;
            }
        }
    }

    for (i=3;i<=MX;i+=2)
    {
        if (!stats[i])
        {
            vp.pb (i);
        }
    }

    vpsz = vp.size();
}

void primefacto(L n)
{
    L i;

    for (i=0;i<vpsz;i++)
    {
        while (n%vp[i]==0)
        {
            facto.pb (vp[i]);
            n/=vp[i];
            if (n==0 or n==1) break;
        }
    }
}

int main()
{
    L n,cnt;
    vector <L> dis;
    map <L,bool> mp;
    prime();
    //for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
    while (sf("%ld",&n)==1 and n)
    {
        primefacto(n); cnt=0;
        //for (L i=0;i<facto.size();i++) cout << facto[i] << " ";
        for (L i=0;i<facto.size();i++)
        {
            if (!mp[facto[i]])
            {
                dis.pb(facto[i]);
            }

            mp[facto[i]] = true;
        }

        for (L i=0;i<dis.size();i++) cnt++;
        pf ("%ld : %ld\n",n,cnt);
        facto.clear(); dis.clear(); mp.clear();
    }

    return 0;
}*/


/*
    Uva 10699 - Count the factors
    Verdict: Accepted
    Time: 0.023

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

bool stats[MX];
L vpsz,cnt;
vector <L> vp;
void prime ()
{
    L i,j,qrt;

    for (i=4;i<=MX;i+=2)
    {
        stats[i] = true;
    }

    qrt = (long) sqrt(double(MX));

    vp.pb (2);
    for (i=3;i<=qrt;i+=2)
    {
        if (!stats[i])
        {
            for (j=i*i;j<=N;j+=i+i)
            {
                stats[j] = true;
            }
        }
    }

    for (i=3;i<=MX;i+=2)
    {
        if (!stats[i])
        {
            vp.pb (i);
        }
    }

    vpsz = vp.size();
}

void primefacto(L n)
{
    L i;

    for (i=0;i<vpsz;i++)
    {
        if (n%vp[i]==0)
        {
            cnt++;

            while (n%vp[i]==0) // find the prime factors
            {
                n/=vp[i];
            }

            if (n==1 or n==0) break;
        }
    }
}

int main ()
{
    L n;
    prime();
    //for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
   while (sf ("%ld",&n) and n)
   {
       cnt = 0;

       primefacto(n);

       pf ("%ld : %ld\n",n,cnt);
   }

   return 0;
}

Comments

Popular posts from this blog

SPOJ-CMG - Collecting Mango

LeetCode Palindrome Number

Hacker Rank The Power Sum