Euler #3 largest prime factor

Question

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<stdio.h>  //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.

Answer 1

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.

Answer 2

On top of the answer by Emily L. you can add a simple primality test as an exit condition for the loop, this will also avoid a lot of iterations.

while(number!=1 && div <= sqrt(number))

Where sqrt(number) is the square root of the number in each iteration.

If \$ n \$ does not have divisors \$ < \sqrt{n} \$, then \$ n \$ is prime and thus you can stop looking for larger prime factors and output \$n\$.

Answer 3

Don't iterate all the way until N

Your current worst case scenario is when number is a very large prime number. When this happens you will try every div from 2 to number. Although skipping even numbers or even 2/3 of the numbers (as suggested by Emily L) will increase your speed by 2x or 3x, you still have to iterate N/3 times which can take a long time.

To avoid this, you should compute Math.sqrt(number) at the start and recompute it whenever number decreases. Whenever div goes above the sqrt, you know that the remaining number is the last prime factor. This turns the \$O(N)\$ algorithm into an \$O(\sqrt N)\$ algorithm.

Answer 4

The better result I've obtained is using the function below (lpf5()). It's based on the primality() function (below) that uses the formulas 6k+1, 6k-1 to individuate prime numbers. All prime numbers >= 5 may be expressed in one of the forms p=k*6+1 or p=k*6-1 with k>0 (but not all the numbers having such a forms are primes). Developing these formulas we can see a sequence like the following:

k=1 5,7
k=2 11,13
k=3 17,19
k=4 23,25*
k=5 29,31
.
.
.
k=10 59,61
k=11 65*,67
k=12 71,73
...

5,7,11,13,17,19,23,25,29,31,...,59,61,65,67,71,73,...

We observe that the difference between the terms is alternatively 2 and 4. Such a results may be obtained also using simple math. Is obvious that the difference between k*6+1 and k*6-1 is 2. It's simple to note that the difference between k*6+1 and (k+1)*6-1 is 4.

The function primality(x) returns x when x is prime (or 0 - take care) and the first divisor occurs when x is not prime.

I think you may obtain a better result inlining the primality() function inside the lpf5() function.

I've also tried to insert a table with some primes (from 1 to 383 - the primes in the first 128 results of the indicated formulas) inside the primality function, but the speed difference is unappreciable.

#include <stdio.h>
#include <math.h>

typedef  long long unsigned int uint64;
uint64 lpf5(uint64 x);
uint64 primality(uint64 x);

uint64 lpf5(uint64 x)
{
    uint64 x_=x;

    while ( (x_=primality(x))!=x)
        x=x/x_;

    return x;
}

uint64 primality(uint64 x)
{
    uint64 div=7,f=2,q;

    if (x<4 || x==5)
        return x;

    if (!(x&1))
        return 2;

    if (!(x%3))
        return 3;

    if (!(x%5))
        return 5;

    q=sqrt(x);
    while(div<=q) {
        if (!(x%div)) {
            return div;
        }
        f=6-f;
        div+=f;
    }

    return x;
}

int main(void) {
    uint64 x,k;

    do {
        printf("Input long int: ");
        if (scanf("%llu",&x)<1)
            break;

        printf("Largest Prime Factor: %llu\n",lpf5(x));
    } while(x!=0);

    return 0;
}

Answer 5

Here is my code based on Emily L's logic. It works and solves all test cases, but I am not very pleased with how long it is.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T,i,np;
    unsigned long long N,div,lpf,maxN;
    scanf("%d",&T);
    for(i=0;i<T;i++){
        scanf("%llu",&N);
        lpf=N;
        while(N%2==0 && N!=1 ){
            N/=2;
            lpf = N;
        }
        if (N==1) lpf=2;
        else{
            while(N%3==0 && N!=1 ){
                N/=3;
                lpf = N;
            }
            if (N==1)lpf=3;
            else{
                for (div=6;(div-1)<=sqrt(N)+1;div+=6){
                    while((N%(div-1))==0 && N!=1){
                        N/=(div-1);
                        if (N==1)lpf=(div-1);
                        else lpf=N;
                    }
                    while((N%(div+1))==0 && N!=1){
                        N/=(div+1);
                        if (N==1)lpf=(div+1);
                        else lpf=N;
                    }
                }
            }
        }
        printf("%llu\n",lpf);
    }
    return 0;
}