[UVa] 10852 - Less Prime

My solution simply simulates what is described in the problem, but if you wanna know how to shorten this code then there is one thing to know, you're looking for x for maximum n%x.

#include <stdio.h>
#define MAX 10000

int ver[MAX+3]={0};
int primes[MAX+3];

int gen() {
    int i, j, k=0;
    for (i=2 ; i<=MAX ; i++) {
        if (!ver[i]) {
            primes[k++]=i;
            for (j=2 ; i*j<=MAX ; j++) {
                ver[i*j]=1;
            }
        }
    }
    return k;
}

int main() {
    int q=gen(), high, low, t, p, i, x, n, max, res;

    scanf("%d",&t);

    while (t--) {
        max = -1;
        res = -1;
        scanf("%d",&n);
        for (i=0 ; i<q && primes[i]<=n ; i++) {
            x = primes[i];
            low = (n-x)/x;
            high = n/x;
            for (p=low ; p<=high ; p++) {
                if (max<(n-p*x)) {
                    max = n-p*x;
                    res = x;
                }
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

[UVa] 294 - Divisors

See the posts did in Math on finding the number of divisors of a given number. The method is simple:
Suppose N = a^x * b^y * c^z
Then the number of its divisors is (x+1)*(y+1)*(z+1)

#include <stdio.h>
#define MAX 50000
#define SWAP(a,b) {int t=a; a=b; b=t;}
int ver[MAX+3]={0};
int primes[MAX+3];

int gen() {
    int i, j, k=0;
    for (i=2 ; i<=MAX ; i++) {
        if (!ver[i]) {
            primes[k++]=i;
            for (j=2 ; i*j<=MAX ; j++) {
                ver[i*j]=1;
            }
        }
    }
    primes[0]=2;
    return k;

}

int nod(int n) {
    if (n==1) return 1;
    if (n<=MAX && !ver[n]) return 2;
    int j, c, count=1, temp;
    for (j=0 ; primes[j]*primes[j]<=n ; j++) {
        temp = primes[j];
        c=1;
        while (n%temp==0) {
            n/=temp;
            c++;
        }
        count*=c;
        if (n==1) return count;
    }
    if (count!=1) return count*2;
    return 2;
}

int main() {
    int p = gen(), i, j, count, max, x, y, u, d, kase;

    scanf("%d",&kase);


    while (kase--) {
        scanf("%d %d",&x,&y);
        u=x; d=y;
        if (d<u) SWAP(d,u);
        count=0;
        max=0;
        j=u;
        for (i=u ; i<=d ; i++) {
            count = nod(i);
            if (max<count) {
                max = count;
                j=i;
            }
        }

        printf("Between %d and %d, %d has a maximum of %d divisors.\n",x,y,j,max);
    }

    return 0;

}

DIUPC 2010, Problem I

#include <stdio.h>
#define MAX 1000000
bool ver[MAX+3]={false};
int primes[MAX+3];
int nods[MAX+3];

int gen() {
    int i, j, k=0;

    for (i=2 ; i<=MAX ; i++) {
        if (ver[i]==false) {
            primes[k++]=i;
            for (j=2 ; i*j<=MAX ; j++) {
                ver[i*j]=true;
            }
        }
    }


    return k;
}

int nod(int n) {

        int i, j, c, count=1, temp;

        for (j=0, c=0 ; primes[j]*primes[j]<=n ; j++) {
            c=1;
            temp=primes[j];
            while (n%temp==0) {
                n/=temp;
                c++;
            }
            count*=c;
        }


        if (n==1) { /*putchar('x');*/ return count; }
        else return count*2;
}

int main() {
    int i, x, y, sum;
    /*clock_t start=clock(), end;*/
    int p=gen();
    /*end=clock();
    printf("Time taken: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);*/

    nods[0]=1;
    nods[1]=2;
    nods[2]=4;
    nods[3]=7;
    nods[4]=12;

    /*for (i=2 ; i<=1000000 ; i++) {
        if (ver[i]==false)
            divs[i]=2;
        else
            divs[i]=nod(i);
        /*printf("%d %d\n",i,divs[i]);
        getchar();
    }*/
    /*end=clock();
    printf("Time taken: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);*/

    for (i=4 ; nods[i-1]<=1000000 ; i++) {
        if (ver[nods[i-1]]==false)
            nods[i]=nods[i-1]+2;
        else
            nods[i]=nods[i-1]+nod(nods[i-1]);
    }

    /*end=clock();
    printf("Time taken: %lf\n",(double)(end-start)/CLOCKS_PER_SEC);*/

    while(scanf("%d %d",&x,&y)) {
        i=0;
        while (nods[i]<x) {
            i++;
        }
        for (i, sum=0 ; nods[i]<=y ; i++) {
            sum++;
        }
        printf("%d\n",sum);
    }
    return 0;

}

Finding the number of Divisors of a Number

You can say that I've hacked through high school system somehow so I didn't know this before. Today, I was trying to solve a problem that I faced in my last day's DIUPC 2010. While solving the problem I found some interesting properties of number that of course kids play for most. Anyways. The facts that I found are as follows:

1. To find if a number is dividable by other number (of course less that it's half) you just need to check till its' square root. Say if the number is N then check till sqrt(N). That because if the number is dividable by numbers bigger than that then you get the same numbers that you used previously to divide it. Just as this. Say we are testing with 9.
Limit = sqrt(9) = 3.
9/1 = 9
9/3 = 3
9/9 = 1 we used that before. 9 is not a good example so let's use 16.
Limit = sqrt(16) = 4.
16/1 = 1
16/2 = 8
16/4 = 4
16/8 = 2 used.
16/16 = 1 used.
Test with other number to find that I've been a stupid all the way till this day.

2. It's not something that I found today but should be noted here. A number is a combination of several primes. Like this:
1x2 = 2
1x2x3 = 6
1x2x3x4[2x2] = 24
No, 1 is not among primes.

3. If a number N is square then it has equal number of factors below and beyond sqrt(N) + the sqrt(N) itself. Check for 4. sqrt(4) = 2. The divisors of 4 are 1, 2, 4. Check for 16. sqrt(16) = 4. The divisors of 16 are 1, 2, 4, 8, 16. But if the number is not square then It doesn't have the same property. Take 15, the divisors of 15 are 1, 3, 5, 15. Below sqrt(15) are 1, 3 and including and above it are 5, 15. It should've had another number to have the same property.

4. If you keep on dividing a number by it's prime factors (till sqrt(N)) and that number is not a square the at the end there will be a prime left out. Such as 6. Divide by 2. Left 3, But next prime 3 is more squared. So left is 3. Take 20, keep dividing by 2.
20/2 = 10
10/2 = 5
End 'cause 5*5=25>5.
So left is 5.
Take 65.
65/3 = 13
End 'cause it's a prime.

I used this program to find these properties which I did during solving a divisor based problem:

int nod(int n) {

        int i, j, c, count=1, temp;

        for (j=0, c=0 ; primes[j]*primes[j]<=n ; j++) {
            c=1;
            temp=primes[j];
            while (n%temp==0) {
                n/=temp;
                c++;
            }
            count*=c;
        }

        if (n==1) { /*putchar('x');*/ return count; }
        else return count*2;
}

This can be easily modified to show all the primes. Check the sections where I multiply the primes and the sections where I decide what to give as output.

Contest diaries 1

It's not the first time that I've been to a contest though but this is the first time that I'm feeling like writing about one. Today, me and my team participated at the Daffodil IUPC 2010, a national level contest in Bangladesh. Teams from almost all renowned varsities came for the title of the championship. Before this, when I participated at the BUBT IUPC 2010, the arena wasn't looking like a contest arena. But this time the arena was awesome. The PCs were stylish and the food was less :[.

Likes:
1 - Nice looking workstations
2 - All the contestants in one room
3 - Setup of the systems.
4 - Nice view with lots of solver balloons in the room

Dislikes:
1 - Very unorganized while the contestants taking seats
2 - A wire beside us was burning because of overload
3 - Too much login issues
4 - Some PCs were so f'd up that the contestants had to submit using USB
5 - The AC was awful
6 - The sound system was a pain to the ear
7 - Too much light hitting the eyes

Top solvers:
As usual, our country's proud, BUETians solved 7 problems. It was a nice start when a team solved a problem at the very first minute with the single submission that was also the first in the contest. I'll give them this, the five balloons idea was great, creating more jealousy and competitiveness among the contestants. At first the Aeternitas team was starting to take the lead but the rat race ended with the slow but clever jumps of the Chimpanzees. As usual first 10 positions were taken by SUST, BUET and DU. Noticeable among the Private Varsities were SUB Epsilons.
The venue was all centered around the arena. I think they should have paid more attention to the capacity of the AC, I was sweating literally. The BUBT Runtime Error team had a plug all burned up beside them and their team mate had to repeatedly call the volunteers about that. Some of the seats were not distributed properly. We had to share one with the BUBTans. The cameras were putting lights on contestants faces at some places.

Solving experience:
We solved 2 problems. One a regular statistics median problem and the other was an ad-hoc XML parser problem.
What I think we should do:
- Find a better way to read the problems faster so that we can detect the easiest problem
- I left freopen intact while submitting which generated errors, I think I should work more carefully on better codes
- It's high time we've been serious about algorithms
- Need to be more mathematically analytic.

That's all I can think of right now.

[SPOJ] Prime Generator [PRIME1]

Methods used, Modified Sieve of Erastosense. Because you have to print the numbers so you have to go to a bit of brute forcing at least to a a minimum level. So first generate all the primes till sqrt(1000000) and then for all n, m go through all the numbers while checking them for divisibility with the primes in your sieve.

#include <stdio.h>
#define SWAP(a,b) {int t = a; a = b; b = t;}
bool ver[32000]={false};
int primes[4000]={0};

int gen() {
    int i, j, k=0;


    for (i=2 ; i<=32000 ; i++) {
        if (ver[i]==false) {
            primes[k++]=i;
            /*printf("%d\n",i);
            getchar();*/
            for (j=2 ; j>0 && i*j<=32000 ; j++) {
                ver[i*j]=true;
            }
        }
    }
    primes[0]=2;
    /*for (i=0 ; i<10 ; i++)
        printf("%d\n",primes[i]);*/

    return k;
}

int main() {
    int p = gen(),t,i,j,low,high;
    bool print;

    scanf("%d",&t);

    while (t--) {
        scanf("%d %d",&low,&high);

        if (high<low)
            SWAP(high,low);
        if (low == 1) low++;
        if (low == 0) low+=2;

        for (i=low ; i<=high ; i++) {
            for (j=0, print=true ; primes[j]*primes[j]<=i ; j++) {
                if (i%primes[j]==0) {
                    print = false;
                    break;
                }
            }
            if (print) printf("%d\n",i);
        }
        printf("\n");
    }


    return 0;
}

[UVa] 10780 - Again Prime? No Time

The main principle behind this problem is ofcourse that "To know if m divides n! you have to find all the prime factors of m in n atleast as many times as they are in m".
But here's another degree of that. You have to get the power of m that divides n!.

Just a simple modification of the original method. Suppose m^k divides n!. So all the prime factors in m^k will be in n.
Now if the prime factorization of m^1 are x^1 x y^1 and m^k divides n! then
prime factorization of m^k is x^(1xk) + y^(1xk). Then finding the minimal level at which the powers of the prime factors of m and n are matched you get k because then the power is common at both the areas.

#include <stdio.h>
#include <math.h>
#define P_MAX 5000
int ver[P_MAX+3]={0};
int prs[P_MAX+3];
int divs[2000][2];
int max(int a, int b) {
    if (a>b) return a;
    else return b;
}
int min(int a, int b) {
    if (a<b) return a;
    else return b;
}

int gen(int lim_HPRIME) {
    int i, j, k=0;

    for (i=4 ; i<=lim_HPRIME ; i+=2) {
        ver[i] = 1;
    }

    for (i=3 ; i<=lim_HPRIME ; i+=2) {
        for (j=i*i ; j>0 && j<=lim_HPRIME ; j+=i*2) {
            ver[j]=1;
        }
    }
    for (i=2 ; i<=lim_HPRIME ; i++) {
        if (!ver[i]) prs[k++]=i;
    }

    return k;
}

int get(int n, int p) {
    int count=0, m=p;

    while (n/m>0) {
        count += n/m;
        m*=p;
    }

    return count;
}


int main() {

    /*freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/

    int nCASES, m, n, dc, res, tmp_m, tmp_n, kount=1, i, p=gen(P_MAX), mx_n, mx_m;
    scanf("%d",&nCASES);

    while (nCASES--) {
        scanf("%d %d",&m,&n);
        printf("Case %d:\n",kount++);

        mx_m = 99999;
        for (i=0, tmp_m=m, tmp_n=n, dc=0 ; i<p && prs[i]<=m ; i++) {

            /*tmp_m = m;*/

            if (tmp_m%prs[i]==0) {
                divs[dc][0]=prs[i];
                divs[dc][1]=0;
                while (tmp_m%prs[i]==0) {
                    divs[dc][1]++;
                    tmp_m/=prs[i];
                }
                /*mx_m = min(mx_m,divs[dc][1]);*/
                dc++;
            }
        }
        if (tmp_m > 1) {
            divs[dc][0] = tmp_m;
            divs[dc][1] = 1;
            dc++;
        }

        /*for (i=0 ; i<dc ; i++) {
            printf("%d %d\n",divs[i][0],divs[i][1]);
        }*/

        mx_n = 99999;
        for (i=0 ; i<dc ; i++) {
            res=get(tmp_n,divs[i][0]);
            mx_n = min(mx_n,res/divs[i][1]);
            if (res<divs[i][1])
                break;
        }
        if (i<dc)
            printf("Impossible to divide\n");
        else {
            printf("%d\n",(int)mx_n);
        }

    }
    return 0;

}