C-greatest prime factor of a given number

Question

I have written the following code to compute the greatest prime factor of a number supplied through standard input but it is taking ages to execute.How can i reduce the execution time of the program?

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool is_prime(unsigned long long num)
{
    if (num == 0 || num == 1)
        return false;
    if (num == 2)
        return true;
    for (unsigned long long j = 2; j < num; j++)
        if(num%j==0)
            return false;

    return true;
}

int main(void)
{
    unsigned long long n,i;
    printf("enter the number: ");
    scanf("%llu",&n);
    for(i=n-1;i>1;i--)
        if((is_prime(i)) && n%i==0)
            break;
    printf("%llu\n",i);

    return 0;
}

Number in the input is 600851475143.

Answer 1

Have fun...one function for all prime factors, one for maximum prime factor:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long u64_t;

static size_t prime_factors(u64_t value, u64_t *array)
{
    size_t n_factors = 0;
    u64_t n = value;
    u64_t i;

    while (n % 2 == 0)
    {
        n /= 2;
        //printf("Factor: %llu (n = %llu)\n", 2ULL, n);
        array[n_factors++] = 2;
    }

    while (n % 3 == 0)
    {
        n /= 3;
        //printf("Factor: %llu (n = %llu)\n", 3ULL, n);
        array[n_factors++] = 3;
    }

    for (i = 6; (i - 1) * (i - 1) <= n; i += 6)
    {   
        while (n % (i-1) == 0)
        {
            n /= (i-1);
            //printf("Factor: %llu (n = %llu)\n", (i-1), n);
            array[n_factors++] = (i-1);
        }
        while (n % (i+1) == 0)
        {
            n /= (i+1);
            //printf("Factor: %llu (n = %llu)\n", (i+1), n);
            array[n_factors++] = (i+1);
        }
    }
    if (n != 1)
        array[n_factors++] = n;

    return n_factors;
}

static u64_t max_prime_factor(u64_t value)
{
    u64_t n = value;
    u64_t i;
    u64_t max = n;

    while (n % 2 == 0)
    {
        n /= 2;
        //printf("Factor: %llu (n = %llu)\n", 2ULL, n);
        max = 2;
    }

    while (n % 3 == 0)
    {
        n /= 3;
        //printf("Factor: %llu (n = %llu)\n", 3ULL, n);
        max = 3;
    }

    for (i = 6; (i - 1) * (i - 1) <= n; i += 6)
    {   
        while (n % (i-1) == 0)
        {
            n /= (i-1);
            //printf("Factor: %llu (n = %llu)\n", (i-1), n);
            max = (i-1);
        }
        while (n % (i+1) == 0)
        {
            n /= (i+1);
            //printf("Factor: %llu (n = %llu)\n", (i+1), n);
            max = (i+1);
        }
    }
    //printf("Max Factor = %llu\n", (n == 1) ? max : n);

    return (n == 1) ? max : n;
}

static void print_factors(u64_t value, size_t n_factors, u64_t *factors)
{
    printf("%20llu:", value);
    int len = 21;
    for (size_t i = 0; i < n_factors; i++)
    {
        if (len == 0)
            len = printf("%.21s", "");
        len += printf(" %llu", factors[i]);
        if (len >= 60)
        {
            putchar('\n');
            len = 0;
        }
    }
    if (len > 0)
        putchar('\n');
}

void builtin_tests(void)
{
    u64_t tests[] =
    {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
        19, 20, 25, 49, 63, 69, 71, 73, 825, 829, 1000, 6857, 73112,
        731122, 7311229, 73112293, 731122935, 7311229357, 73112293571,
        600851475143, 731122935711, 7311229357111,
        18446744073709551610ULL, 18446744073709551611ULL,
        18446744073709551612ULL, 18446744073709551613ULL,
        18446744073709551614ULL, 18446744073709551615ULL,
    };
    u64_t factors[64];

    for (size_t i = 0; i < sizeof(tests)/sizeof(tests[0]); i++)
    {
        u64_t max = max_prime_factor(tests[i]);
        printf("%20llu -> Max Prime Factor = %llu\n", tests[i], max);
        size_t n_factors = prime_factors(tests[i], factors);
        print_factors(tests[i], n_factors, factors);
    }
}

int main(int argc, char **argv)
{
    if (argc == 1)
        builtin_tests();
    else
    {
        for (int i = 1; i < argc; i++)
        {
            u64_t factors[64];
            u64_t value = strtoull(argv[i], 0, 0);
            u64_t max = max_prime_factor(value);
            printf("%20llu -> Max Prime Factor = %llu\n", value, max);
            size_t n_factors = prime_factors(value, factors);
            print_factors(value, n_factors, factors);
        }
    }
    return 0;
}

Results

                   1 -> Max Prime Factor = 1
                   1:
                   2 -> Max Prime Factor = 2
                   2: 2
                   3 -> Max Prime Factor = 3
                   3: 3
                   4 -> Max Prime Factor = 2
                   4: 2 2
                   5 -> Max Prime Factor = 5
                   5: 5
                   6 -> Max Prime Factor = 3
                   6: 2 3
                   7 -> Max Prime Factor = 7
                   7: 7
                   8 -> Max Prime Factor = 2
                   8: 2 2 2
                   9 -> Max Prime Factor = 3
                   9: 3 3
                  10 -> Max Prime Factor = 5
                  10: 2 5
                  11 -> Max Prime Factor = 11
                  11: 11
                  12 -> Max Prime Factor = 3
                  12: 2 2 3
                  13 -> Max Prime Factor = 13
                  13: 13
                  14 -> Max Prime Factor = 7
                  14: 2 7
                  15 -> Max Prime Factor = 5
                  15: 3 5
                  16 -> Max Prime Factor = 2
                  16: 2 2 2 2
                  17 -> Max Prime Factor = 17
                  17: 17
                  18 -> Max Prime Factor = 3
                  18: 2 3 3
                  19 -> Max Prime Factor = 19
                  19: 19
                  20 -> Max Prime Factor = 5
                  20: 2 2 5
                  25 -> Max Prime Factor = 5
                  25: 5 5
                  49 -> Max Prime Factor = 7
                  49: 7 7
                  63 -> Max Prime Factor = 7
                  63: 3 3 7
                  69 -> Max Prime Factor = 23
                  69: 3 23
                  71 -> Max Prime Factor = 71
                  71: 71
                  73 -> Max Prime Factor = 73
                  73: 73
                 825 -> Max Prime Factor = 11
                 825: 3 5 5 11
                 829 -> Max Prime Factor = 829
                 829: 829
                1000 -> Max Prime Factor = 5
                1000: 2 2 2 5 5 5
                6857 -> Max Prime Factor = 6857
                6857: 6857
               73112 -> Max Prime Factor = 37
               73112: 2 2 2 13 19 37
              731122 -> Max Prime Factor = 52223
              731122: 2 7 52223
             7311229 -> Max Prime Factor = 24953
             7311229: 293 24953
            73112293 -> Max Prime Factor = 880871
            73112293: 83 880871
           731122935 -> Max Prime Factor = 89107
           731122935: 3 5 547 89107
          7311229357 -> Max Prime Factor = 7311229357
          7311229357: 7311229357
         73112293571 -> Max Prime Factor = 8058227
         73112293571: 43 211 8058227
        600851475143 -> Max Prime Factor = 6857
        600851475143: 71 839 1471 6857
        731122935711 -> Max Prime Factor = 4973625413
        731122935711: 3 7 7 4973625413
       7311229357111 -> Max Prime Factor = 12939061
       7311229357111: 547 1033 12939061
18446744073709551610 -> Max Prime Factor = 1504703107
18446744073709551610: 2 5 23 53301701 1504703107
18446744073709551611 -> Max Prime Factor = 287630261
18446744073709551611: 11 59 98818999 287630261
18446744073709551612 -> Max Prime Factor = 2147483647
18446744073709551612: 2 2 3 715827883 2147483647
18446744073709551613 -> Max Prime Factor = 364870227143809
18446744073709551613: 13 3889 364870227143809
18446744073709551614 -> Max Prime Factor = 649657
18446744073709551614: 2 7 7 73 127 337 92737 649657
18446744073709551615 -> Max Prime Factor = 6700417
18446744073709551615: 3 5 17 257 641 65537 6700417

Answer 2

bool is_prime(unsigned long long num)
{
    if (num <  2) return false;      /* Reject border cases */

    if (num == 2) return true;       /* Accept the largest even prime */

    if ((num & (~1)) == num) return false;  /* Reject all other evens */

    unsigned long long limit = sqrt(num) + 1;  /* Limit the range of the search */

    for (unsigned long long j = 3; j < limit; j += 2)  /* Loop through odds only */
        if(num % j==0)
            return false;           /* Reject factors */

    return true;                    /* No factors, hence it is prime */

}

Answer 3

The if statement in the loop in main() should check n%i==0 first so that non-factors are not checked for primeness. This alone makes the program over 200 times faster on all the numbers from 1 to 2000 on a simple test case I ran on a modern Intel CPU. The mod below just to main() (I broke it out into a function returning the largest prime factor) improves the speed significantly more. I also consider the number itself as a possible factor (not done in the original).

unsigned long long largest_prime_factor(unsigned long long n)

    {
    unsigned long long i,sqrtn,maxprime;

    if (is_prime(n))
        return(n);
    sqrtn=(unsigned long long)sqrt((double)n);
    maxprime=1;
    for (i=2;i<=sqrtn;i++)
        {
        if (n%i==0)
            {
            unsigned long long f;

            f=n/i;
            if (is_prime(f))
                return(f);
            if (is_prime(i))
                maxprime=i;
            }
        }
    return(maxprime);
    }

Answer 4

keeping the same logic you can reduce time by executing loop till sqrt(num) only. because if it is not prime, there would be at least one divisor which is less then sqrt(num).

Let's take num is not prime. so for some 1< a < num, a*b = num.

so either a or b should be less than sqrt(num).

Hence your code be for is_prime should be changed to the one as follows

bool is_prime(unsigned long long num)
{
    if (num == 0 || num == 1)
        return false;
    if (num == 2)
        return true;
    long long root_num = sqrt(num);
    for (unsigned long long j = 2; j < root_num; j++)
        if(num%j==0)
            return false;

    return true;
}

Now if you want to change your logic, then there is an algorithm called sieve method which finds all prime numbers which are less than given number. check this out Sieve Algorithm

Answer 5

Its better to start for loop from square root of number to 3, again you can skip even numbers.

so that you can get answer within small time..