1.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 11876 - N + NOD (N)
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2987

 *
  * @author Felix Dietrich
 * @version 1.0, 24.10.2010
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 1.872
 *
 * The commented code gives a HashMap<i,set> with a set "set" of the divisors of each number i.
 */
import java.util.Scanner;

public class Main
{
    public static final int MAX = (int) 1000;
    public static final boolean[] isPrime = new boolean[MAX + 1];
    public static final int prime[] = new int[MAX];
    public static int maxPrime = 0;
//    private static Map<Integer,Set<Integer>> divisors = new HashMap<Integer,Set<Integer>>();

    private static void sievePrimes()
    {
//        Set<Integer> s = new HashSet<Integer>();
       
        for (int i = 2; i <= MAX; i++)
        {
            isPrime[i] = true;
        }
        // sieve the multiples of 2
        for (int i = 4; i <= MAX; i += 2)
        {
            isPrime[i] = false;
            /*if(!divisors.containsKey(i))
                divisors.put(i, new HashSet<Integer>());
            s = divisors.get(i);
            s.add(1);
            s.add(i);
            s.add(2);
            s.add(i/2);*/
        }

        prime[maxPrime++] = 2;
/*
        s = new HashSet<Integer>();
        s.add(1);
        divisors.put(0, s);
        divisors.put(1, s);
        s = new HashSet<Integer>();
        s.add(1);
        s.add(2);
        divisors.put(2, s);*/

        // sieve other numbers
        int squareRoot = (int) Math.sqrt(MAX);
        for (int i = 3; i <= MAX; i += 2)
            if (isPrime[i])
            {
                prime[maxPrime++] = i;
//                s = new HashSet<Integer>();
//                s.add(1);
//                s.add(i);
//                divisors.put(i, s);
                for (int j = i + i; j <= MAX; j += i)
                {
                    isPrime[j] = false;
                    //if(!divisors.containsKey(j))
                    //    divisors.put(j, new HashSet<Integer>());
                    //s = divisors.get(j);
                    //s.add(1);
                    //s.add(j);
                    //s.add(i);
                    //s.add(j/i);
                }
            }

    }

    private static int calc(int n)
    {
        if(n == 0)
            return 1;
       
        //if(divisors.containsKey(n))
        //    return divisors.get(n).size();
       
        int d = 1, power;
        for (int i = 0; i < maxPrime; i++)
            if (n % prime[i] == 0)
            {
                // System.out.println(n + " ==> " + prime[i]);
                power = 1;
                while (n % prime[i] == 0)
                {
                    n /= prime[i];
                    power++;
                    // System.out.println("    " + prime[i]);
                }
                d *= power;
            }

        if (n != 1)
            return d * 2;

        return d;
    }

    public static void main(String... s)
    {
        // calculate divisors and NOD series
        sievePrimes();

        //long dist = System.currentTimeMillis();
        int[] abs = new int[1000600];
        int cab = 1;

        int newnod = 1;
        abs[0] = 0;
        abs[1] = 1;
        abs[2] = 1;
        for (int i = 1; i < 64750; i++)
        {
            newnod = newnod + calc(newnod);
            for(int c2=cab+1;c2<=newnod;c2++)
                abs[c2] = abs[cab];
            abs[newnod] = abs[cab]+1;
            cab = newnod;
        }

        Scanner sc = new Scanner(System.in);
        //dist = System.currentTimeMillis() - dist;
        //System.out.println(dist);

        int tcs = sc.nextInt();
        int A,B,count;
        for (int c = 0; c < tcs; c++)
        {
            A = sc.nextInt();
            B = sc.nextInt();
            count = abs[B]-abs[A-1];
           
            System.out.println("Case " + (c+1) + ": " + count);
        }
    }
}

2.

/*
 * ACM Contest training
 * Problem: 11876 - N + NOD (N)
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=226&problem=2987
 *
 * @author Christoph Goettschkes
 * @version 1.0, 10/27/2010
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 1.492
 */

import java.io.*;
import java.util.*;

class Main
{

    public static int[] sieve = new int[1000001];
    public static List<Integer> seq = new ArrayList<Integer>();
    public static List<Integer> comp = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception
    {
       
        for (int i = 1; i <= 1000000; i++) {
            for (int j = i; j <= 1000000; j+=i) {
                sieve[j]++;
            }
        }

        seq.add(1);
        int last = 1;
        for (int i = 0; i <= 1000000; i++) {
            if (last > 1000000)
                break;
            int cur = last + sieve[last];
            seq.add(cur);
            last = cur;
        }

        int curKey = 0;
        int counter = 0;
        comp.add(0);
        for (int i = 1; i <= 1000000; i++) {
            if (i == seq.get(curKey)) {
                curKey++;
                counter++;
            }
            comp.add(counter);
        }
        StringBuilder result = new StringBuilder();

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int testCases = Integer.parseInt(reader.readLine().trim());

        for (int i = 1; i <= testCases; i++) {
            String[] lineArr = reader.readLine().split("\\s");
            result.append("Case " + i + ": " + test(Integer.parseInt(lineArr[0]), Integer.parseInt(lineArr[1])) + "\n");
        }
        System.out.print(result);
    }

    public static int test(int start, int end) {
        return comp.get(end) - comp.get(start - 1);
    }

}


3.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest
 * Problem:     11876 - N + NOD (N)
 * Link:        http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2987
 *
 *
 * Method :     prime sieve + cache
 * Status :     Accepted
 * Runtime:     1.404
 *
 * @author      Evgeni Pavlidis
 * @version     1.0, 25/10/2010
 */


import java.io.*;
import java.util.*;

class Main
{

    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws IOException
    {
        st.nextToken();
        return (int)st.nval;
    }

    static int MAX = 1000001;
    static int LIMIT = (int)Math.sqrt(MAX)+1;
    static boolean[] isPrime = new boolean[LIMIT];
    static int[] prime = new int[LIMIT];
    static int maxPrime = 0;

    static void sievePrimes()
    {
        isPrime[2] = true;
        for(int i = 3; i < LIMIT; i+=2)
            isPrime[i] = true;

       
        for(int i = 3; i <= 100; i+=2)
            if(isPrime[i])
                for(int j = i + i; j < LIMIT; j+= i)
                    isPrime[j] = false;

        for(int i = 2; i < LIMIT; i++)
            if(isPrime[i])
                prime[maxPrime++] = i;
    }

    static int nod(int n)
    {
        int divisors = 1;
        int power;


        for(int i = 0; i < maxPrime; i++)
            if(n % prime[i] == 0)
            {
                power = 0;
                while(n % prime[i] == 0)
                {
                    power++;
                    n /= prime[i];
                }
               
                divisors *= power+1;
            }

        if(n > 1)
            divisors *= 2;

        return divisors;
    }

    public static void main(String...args) throws IOException
    {
        int a,b;
        StringBuffer output = new StringBuffer();

        sievePrimes();

        int[] n = new int[MAX+1];
        int[] cache = new int[MAX+1];

        n[0] = 1;
        n[1] = 2;
        n[2] = 4;
        for(int i = 3; n[i-1] <= MAX; i++)
            n[i] = n[i-1] + nod(n[i-1]);

        int pos = 0;
        for(int i = 1; i <= MAX; i++)
        {
            if(n[pos] == i)
                pos++;

            cache[i] = pos;
        }

        int testCases = nextInt();
        for(int tc = 1; tc <= testCases; tc++)
        {
            a = nextInt();
            b = nextInt();

            output.append(String.format("Case %d: %d\n", tc, cache[b] - cache[a-1]));
        }

        System.out.print(output);
    }
}