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