C/project_euler/problem_3/sol1.c at e5dad3fa8def3726ec850ca66a7f51521f8ad393 · TheAlgorithms/C · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * \file
 * \brief [Problem 3](https://projecteuler.net/problem=3) solution
 *
 * Problem:
 *
 * The prime factors of 13195 are 5,7,13 and 29. What is the largest prime
 * factor of a given number N? e.g. for 10, largest prime factor = 5. For 17,
 * largest prime factor = 17.
 */
#include <math.h>
#include <stdio.h>

/** Check if the given number is prime */
char isprime(int no)
{
    int sq;

    if (no == 2)
    {
        return 1;
    }
    else if (no % 2 == 0)
    {
        return 0;
    }
    sq = ((int)(sqrt(no))) + 1;
    for (int i = 3; i < sq; i += 2)
    {
        if (no % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

/** Main function */
int main()
{
    int maxNumber = 0;
    int n = 0;
    int n1;
    scanf("%d", &n);
    if (isprime(n) == 1)
        printf("%d", n);
    else
    {
        while (n % 2 == 0)
        {
            n = n / 2;
        }
        if (isprime(n) == 1)
        {
            printf("%d\n", n);
        }
        else
        {
            n1 = ((int)(sqrt(n))) + 1;
            for (int i = 3; i < n1; i += 2)
            {
                if (n % i == 0)
                {
                    if (isprime((int)(n / i)) == 1)
                    {
                        maxNumber = n / i;
                        break;
                    }
                    else if (isprime(i) == 1)
                    {
                        maxNumber = i;
                    }
                }
            }
            printf("%d\n", maxNumber);
        }
    }
    return 0;
}