Euler #3 largest prime factor

Problem Statement

This problem is a programming version of Problem 3 from projecteuler.net


The prime factors of 13195 are 5, 7, 13 and 29.


What is the largest prime factor of a given number N?


Input Format First line contains T, the number of test cases. This is followed by T lines each containing an integer N.


Output Format


For each test case, display the largest prime factor of N.


Constraints


\$1 \le T \le 10\$


\$10 \le N \le 10^{12}\$

#include  //C language
int main()
{
long long  number; //Declaring Variables 
int cases;
scanf("%d",&cases);
while(cases--)
{
    scanf("%lld",&number);
    long long div=2, ans = 0, maxFact;
    while(number!=0)
        {
            if(number % div !=0)
                div = div + 1;
            else
            {
                maxFact  = number;
                number = number / div;

                if(number == 1)
                    {
                        printf("%lld\n",maxFact);
                        ans = 1;
                        break;
                    }
            }
        }
 }
 return 0;
}

How can the speed be increased? This code gives me timeout error in the last test case of HackerRank.

Use properties of prime numbers

The only prime number that is even is 2, for the simple reason that if the number is even, it is evenly divisible by 2 and is thus not a prime.

So after checking if 2 is a factor and removing it, simply start with div = 3 and in the update do div = div + 2. And you're twice as fast!

But there is more, consider \$x=6k+l\$ where \$l\in\left[0,5\right]\in \mathcal{Z}\$ and \$k\ge 0\$. It's obvious \$x\$ can represent any positive integer.

Assume for a second that \$k>0\$ and let's look a bit closer:

• \$x=6k+0\$ is always be divisible by 2 and 3.

• \$x=6k+1\$ This might be a prime (7, 13 for example are primes).

• \$x=6k+2=2\cdot (3k+1)\$ is always divisible by 2.

• \$x=6k+3=3\cdot (2k+1)\$ is always divisible by 3.

• \$x=6k+4=2\cdot(3k+2)\$ is always divisible by 2.

• \$x=6k+5\$ This might be a prime (11, 19 for example are primes).

Now note that \$6k+5 = 6\left(k+1\right)-1\$ so after checking the divisors we would miss at the start (2 and 3) set div=6 and try division with div-1 and div+1 then increase div by six and repeat.

This means that you're skipping 2/3rds of all divisors, i.e. ~300% faster.
Your exit condition for the loop is useless

As the input is guaranteed larger than zero, number!=0 will always be true in your loop condition. In fact you can reduce branching even further like this:

while(number!=1){
    while(number % div == 0){
        number = number / div;
        maxFact = div;
    }
    div = div + 1;
}
printf("%lld\n",maxFact);
ans = 1;

that's one branch less per iteration.

StackExchange Code Review Q#90492, answer score: 14