CodeForces Freshman exercise There are 60 submissions from me to the very first beginner-freshman exercise at codeforces.com. Problem: 100985A - MaratonIME helps Pablito

I don't pass the tests because of Time limit exceeded (tle). I'm just thinking about the test can't be passed using java because of performance. But really, I think a crappy error in my algorithm is more likely. Or my approach is completely wrong. So feel free to comment my approach.

Excercise:


  As is well known by any cultured person, rats are the smartest beings
  on earth. Followed directly by dolphins.
  
  MaratonIME knows about the species hierarchy and uses this knowledge
  in it's regard. Usually, when they need some resource, they know it's
  always useful to have a smart rat available. Unfortunately, rats are
  not very fond of us, primates, and will only help us if they owe us
  some favour.
  
  With that in mind, MaratonIME decided to help a little rat called
  Pablito. Pablito is studying rat's genealogy, to help with cloning and
  genetic mapping. luckily, the way rats identify themselves make the
  job much easier.
  
  The rat society is, historically, matriarchal. At first, there were
  little families, each of which had it's own leading matriarch. At that
  time, it was decided that rats would organize themselves according to
  the following rules:
  
  Each martiarch had an id number greater than one. Each of these ids
  were chosen in a way such that they would have the least amount of
  divisors possible. Each family member had the same id as the
  matriarch. The id of any newborn rat would be the product of its
  parents id's. For instance, the offspring of a rat with id 6 and
  another with id 7 is 42.
  
  Pablito needs to know if two given rats have a common ancestor, but
  his only tool is the id number of each of the two rats, which is
  always a positive integer greater than 1 with no more than 16 digits.
  Can you help him?
  
  Create a program that decides if a pair of rats have some common
  ancestor.
  
  Input The input begins with a positive integer t ≤ 105, the number of
  test cases.
  
  After that, follows t lines, each with two integers ai e bi
  identifying two rats.
  
  Every rat's id is a positive integer greater than 1 and with no more
  than 16 digits.
  
  Output For each test case, print "Sim" if the rats ai and bi share a
  common ancestor and "Nao" otherwise.


My latest approach before using multiple threads. (Yeah, TLE there as well).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class A {
    public static void main(String[] args) throws IOException{
        BufferedReader scan = new BufferedReader (new InputStreamReader(System.in));
        int amountTests = Integer.parseInt(scan.readLine());

        for (int i = 0; i&lt;amountTests; i++){
            String[] tmp = scan.readLine().split(" ");
            long l1 = Long.parseLong(tmp[0]);
            long l2 = Long.parseLong(tmp[1]);
            if (l1 &lt; l2){
                searchPrims(l1,l2);     
            }else{
                searchPrims(l2,l1);     
            }
        }
    }

    static void searchPrims(long n, long n2){
        int d = 2;
        while (true){
            if(n%d==0){
                if(n2%d==0){
                    System.out.println("Sim");
                    return;
                }
                n/=d;
                d = 2;
            }
            else if(n==1){
                System.out.println("Nao");
                return;
            }
            else{
                if(d==2)
                    d=3;
                else{
                    d+=2;
                }
            }
        }
    }
}
Improving what you have


                d = 2;



Part of the problem is this line.  Each time you find a matching divisor, you restart from the beginning.  This isn't necessary.  The code works without this.  Once you've removed all the 2s, nothing will put them back.  


    static void searchPrims(long n, long n2){
        int d = 2;
        while (true){
            if(n%d==0){
                if(n2%d==0){
                    System.out.println("Sim");
                    return;
                }
                n/=d;
                d = 2;
            }
            else if(n==1){
                System.out.println("Nao");
                return;
            }
            else{
                if(d==2)
                    d=3;
                else{
                    d+=2;
                }
            }
        }
    }



I would find this easier to read as

    static boolean searchCommonFactors(long n, long n2){
        for (int d = 3; n &gt;= d; d += 2) {
            if (n % d == 0) {
                if (n2 % d == 0) {
                    return true;
                }

                do {
                    n /= d;
                } while (n % d == 0);
            }
        }

        return n % 2 == 0 &amp;&amp; n2 % 2 == 0;
    }


This returns a boolean value instead of printing.  So we would have to print outside it.  Something like 

    static void printAnswer(boolean answer) {
        System.out.println(answer ? "Sim" : "Nao");
    }


This way we can split up the returns more naturally.  Also, this would be reusable in other problems with different output requirements.  

This way we don't keep checking if n2 is divisible by a factor.  We check once.  If it is, we return immediately.  If it isn't, we know it never will be.  We discard all of that factor to reduce the maximum size of d.  

Putting the even check at the end takes the special behavior out of the loop.  This way we can simplify the loop iteration.  

We could get back some efficiency by putting that check first and then removing all the 2s from n.  

        if (n % 2 == 0 &amp;&amp; n2 % 2 == 0) {
            return true;
        }

        while (n % 2 == 0) {
            n /= 2;
        }


Alternative approaches

Your approach basically factors the smaller number.  If one of its factors is also a factor of the other number, you say that they are related.  

A more efficient approach might be to use the Euclidean algorithm to see if the two numbers have a greatest common divisor (GCD) larger than 1.  So you'd say something like 

    printAnswer(gcd(l1, l2) &gt; 1);


to get the answer.  

A little searching finds a gcd implementation:  

public static long gcd(long a, long b) {
    while ( 0 != b ) {
        long temp = a;
        a = b;
        b = temp % b;
    }

    return a;
}


There's a relatively elegant recursive solution. 

public static long gcd(long a, long b) {
    return (b == 0) ? a : gcd(b, a % b);
}


But the iterative version should normally be faster.  

I would expect this to be faster than your code, as it reduces a and b to the greatest common factor rather than searching out every factor of a only to find that none of them match.