Program isn't terminating for a specific input-CodePudding

I am trying to write a program that will let me know if a number has the odd divisor greater than one. Let's n be the number, and x be the divisor. x%2!=0 and x>1; Code:

import java.util.Scanner;
public class Simple1{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long n;
        for(int i=0; i<t; i  ) {
            n=sc.nextLong();
            if(n<3)System.out.println("NO");
            else {
                
                if(n%2!=0)System.out.println("YES");
                else {
                    int ans=0;
                    for(long j=3; j<=n/2; j =2) {
                        if(n%j==0) {
                            ans=1;
                            break;
                        }
                    }
                    if(ans==1)System.out.println("YES");
                    else System.out.println("NO");
                }
                
            }
        }
    }
}

This java code works fine. But it's not working for a specific input.. and that is n = 1099511627776. If I change the last digit to any int other than 6, then it works fine and gives output. Even numbers greater than that works. But only this number n=1099511627776, when I input this to my program, no terminating happens and no output. Help me to figure out what happens here.

CodePudding user response：

The number 1099511627776 is two to the power 40. That means it has to check through the whole big for-loop to find no odd factors. You would get the same problem, to different extents, with 2199023255552 (2 to the 41) and 549755813888 (2 to the 39). You have to wait longer if you want to do it this way.

A much faster way is to divide n by 2 until you get an odd number.

E.g.

long n = sc.nextLong();
while (n > 1 && n % 2 == 0) {
   n /= 2;
}
if (n > 1) {
    System.out.println("Yes.");
} else {
    System.out.println("No.");
}

An even faster way to tell if a number is a power of two is a bit-twiddling hack:

// Powers of 2 have the property that n & (n-1) is zero
if ((n & (n - 1)) != 0) {
    System.out.println("Yes.");
} else {
    System.out.println("No.");
}

CodePudding user response：

Can you get rid of the powers of two another way?

long number = 1099511627776l;
long r = number >> Long.numberOfTrailingZeros(number);

Then r is an odd divisor, which might be greater than one.

If you think in base 10, then you know a number is divisible by ten if has a trailing zero. You can remove all of the powers of 10 by removing all of the zeros. It is the same for base 2, you can remove all of the factors of 2 by removing all of the trailing zeros (in binary representation).