CodeForces Freshman exercise
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.