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 :

C

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

intis_prime(longlongunsignedintnum)

{

longlongunsignedinti=0;

if(num==1)return1;

if(num==2)return1;

if(!(num%2))return0;

for(i=3;i*i<=num;i+=2)

{

if(!(num%i))

return0;

}

return1;

}

intmain()

{

intfactors[1000];/* Lets assume there are hundred factors for the number */

intfac_count=0;

intlargest_fac=0;

intprime_count=0;

inti=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);

return0;

}

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 !

Jeswin Augustine

I 'm a computer science graduate from Karunya University and I 'm a developer/designer. Born and brought up in India, I have worked with clients all around the globe.This blog serves as an informal and unorganized repository of things I ’ve worked on in my free time. It is mostly about programming for the web and sometimes for desktop application.