# Euler Problem 3: Largest prime factor : C Programming Solution

**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 :**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/* 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; } |

**6857**