Euler Problem 3: Largest prime factor : C Programming Solution

No Comments

Problem :

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

What is the largest prime factor of the number 600851475143 ?

Solution Approach :

Simple approach would be to identify all the prime numbers under the square root of the number 600851475143 which divide the the number 600851475143. When you find a prime factor using this method, keep the track of largest such number to get our result.

Solution :

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

What is the largest prime factor of the number 600851475143 ?
*/

#include "stdio.h"

#define NUMBER 600851475143ULL

int is_prime(long long unsigned int num)
{
    long long unsigned int i=0;

    if( num == 1) return 1;
    if( num == 2) return 1;
    if( !(num % 2) ) return 0;

    for(i=3;i*i<=num;i+=2)
    {
        if( !(num%i))
            return 0;
    }

    return 1;

}



int main ()
{

    int factors[1000]; /* Lets assume there are hundred factors for the number */
    int fac_count   = 0;
    int largest_fac = 0;
    int prime_count = 0;
    int i=1;
    while ( i*i < NUMBER )
    {
        if ( is_prime(i) && !(NUMBER%i))
        {
            factors[fac_count] = i;
            fac_count++;
            if(largest_fac < i)
                largest_fac = i;
        }
        i++;
    }
    printf (" factors of the" NUMBER " are : ");
    for(i =0;i<fac_count;i++)
    {
        printf(" %d ", factors[i]);
    }

    printf("\n Largest Factor of "NUMBER" %d  \n ",largest_fac);

    return 0;
}


Answer: 6857
Let me know your approach you happen to find a better way to solve this using C programming in the comment section below.
Happy coding !
Categories: Programming

Leave a Reply

Your email address will not be published. Required fields are marked *

*

code