Category Archives: Bad Algorithm

(UVa) 146 – ID Codes

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=82
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;


int main()
{
    string ss;
    while(true)
    {
        cin>>ss;
        if(ss == "#") break;
        if( !next_permutation(all(ss)))
        {
            pf("No Successor\n");
        }
        else
        {
            cout<<ss<<endl;
        }
    }

    return 0;
}

(UVa) 10539 – Almost Prime Numbers

0
Posted on by 
/*
user: php
time: 1.548 sec (I don't know why??)
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1480
*/

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

#define MAXX 1000000
#define SZ 78498

int listOfPrimes[SZ];
bool isPrime[MAXX];

void genaratePrimes()
{
    int *p = listOfPrimes;
    int root = sqrt(MAXX) + 1;

    for(int i=3; i<MAXX; i+=2) isPrime[i] = true;


    for(int i=3; i<root; i += 2)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<MAXX; j+=2*i)
            {
                isPrime[j] = false;
            }
        }
    }
    *p++ = 2;

    for(int i=3; i<MAXX; i+=2)
    {
        if(isPrime[i])
        {
            *p++ = i;
        }

    }
    return;
}






int main()
{
    genaratePrimes();

    long long low, high;
    int kases, introot, count, *p;

    int multiple;

    scanf("%d", &kases);


    double loghigh, loglow, logprime;

    while(kases--)
    {
        scanf("%lld %lld", &low, &high);

        count = 0;

        introot = int(sqrt(high)) + 1;

        p = listOfPrimes;

        while(*p < introot )
        {

            logprime = log(*p);
            loglow = log(low) / logprime;
            loghigh = log(high) / logprime;

            if(loglow < 2)
            {
                loglow = 2;
            }

            if(loghigh < 2)
            {
                loghigh = 2;
            }



            count += (int(loghigh) - int(loglow));

            if(int(loglow) == loglow)
            {
                count++;
            }


            p++;
        }

        printf("%d\n", count);
    }
    return 0;
}