problems 3 - 9

15 files changed, 390 insertions, 0 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 7e1b6b9..c39f493 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,3 +1,10 @@
 cmake_minimum_required(VERSION 2.8)
 add_subdirectory(p1)
 add_subdirectory(p2)
+add_subdirectory(p3)
+add_subdirectory(p4)
+add_subdirectory(p5)
+add_subdirectory(p6)
+add_subdirectory(p7)
+add_subdirectory(p8)
+add_subdirectory(p9)
diff --git a/p3/CMakeLists.txt b/p3/CMakeLists.txt
new file mode 100644
index 0000000..5f57337
--- /dev/null
+++ b/p3/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem3 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p3 ${SOURCES})
+TARGET_LINK_LIBRARIES(p3 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
\ No newline at end of file
diff --git a/p3/main.c b/p3/main.c
new file mode 100644
index 0000000..c72ba35
--- /dev/null
+++ b/p3/main.c
@@ -0,0 +1,30 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+
+#include "utils.h"
+
+int main(int argc, char **argv)
+{
+    // 90 = 2*3*3*5
+    // 17 = 17
+    // 147 = 3*7*7
+
+    long number = 600851475143;
+
+#include "primes_10000000.h"
+
+    list_t *factors = prime_factors_naive(prime_table, prime_table_size,
+        number);
+
+    list_t *curr = factors;
+    while (curr)
+    {
+        printf("%ld\n", *((long*)curr->value));
+        curr = curr->next;
+    }
+
+    list_free(factors, &list_free_long);
+
+    return 0;
+}
diff --git a/p4/CMakeLists.txt b/p4/CMakeLists.txt
new file mode 100644
index 0000000..ba228e5
--- /dev/null
+++ b/p4/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem4 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p4 ${SOURCES})
+TARGET_LINK_LIBRARIES(p4 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p4/main.c b/p4/main.c
new file mode 100644
index 0000000..0931535
--- /dev/null
+++ b/p4/main.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "utils.h"
+
+list_t *digits(int i)
+{
+    list_t *lst = NULL;
+
+    while (i > 0)
+    {
+        int digit = i % 10;
+        i = i / 10;
+        lst = list_append_int(lst, digit);
+    }
+
+    return lst;
+}
+
+int is_palindrome(int i)
+{
+    list_t *d = NULL;
+    int len = 0;
+    int j = 0;
+
+    if (i < 10)
+        return 1;
+
+    d = digits(i);
+    len = list_len(d);
+
+    // printf("i:%d\n", i);
+
+    for (j = 0; j < len/2; ++j)
+    {
+        int *a = (int*)list_get_n(d, j);
+        int *b = (int*)list_get_n(d, len-1-j);
+
+        // printf("a:%d b:%d\n", *a, *b);
+
+        if (*a != *b)
+        {
+            return 0;
+        }
+    }
+
+    list_free(d, list_free_int);
+
+    return 1;
+}
+
+int main(int argc, char **argv)
+{
+    int i, j;
+
+    for (i = 999; i >= 900; i--)
+    {
+        for (j = 999; j >= 900; j--)
+        {
+            int k = i*j;
+
+            if (is_palindrome(k))
+            {
+                printf("%d * %d = %d\n", i, j, k);
+                return 0;
+            }
+        }
+    }
+
+    return 0;
+}
\ No newline at end of file
diff --git a/p5/CMakeLists.txt b/p5/CMakeLists.txt
new file mode 100644
index 0000000..5a700c8
--- /dev/null
+++ b/p5/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem5 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p5 ${SOURCES})
+TARGET_LINK_LIBRARIES(p5 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p5/main.c b/p5/main.c
new file mode 100644
index 0000000..47759c4
--- /dev/null
+++ b/p5/main.c
@@ -0,0 +1,42 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+void basic()
+{
+    long int i = 0;
+    long int j;
+    int done = 0;
+
+    while (!done)
+    {
+        i += 20;
+
+        done = 1;
+
+        // 20 (2*2*5)       2, 4, 10, 20
+        // 19
+        // 18 (2*3*3)       2, 6, 9, 18
+        // 17
+        // 16 (2*2*2*2)     2, 4, 8, 16
+        // 15 (3*5)         3, 5
+        // 14 (2*7)         2, 7
+        // 13
+        // 12 (2*2*3)       2, 3
+        // 11
+        // no need to check for 1-9, because they are included in the
+        // numbers above
+
+        for (j = 11; j <= 20 && done; ++j)
+        {
+            done = done && (i % j == 0);
+        }
+    }
+
+    printf("%ld\n", i);
+}
+
+int main(int argc, char **argv)
+{
+    basic();
+    return 0;
+}
\ No newline at end of file
diff --git a/p6/CMakeLists.txt b/p6/CMakeLists.txt
new file mode 100644
index 0000000..31b0a58
--- /dev/null
+++ b/p6/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem6 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p6 ${SOURCES})
+TARGET_LINK_LIBRARIES(p6 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p6/main.c b/p6/main.c
new file mode 100644
index 0000000..401ff7a
--- /dev/null
+++ b/p6/main.c
@@ -0,0 +1,20 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+int main(int argc, char **argv)
+{
+    long i=0, sum1=0, sum2=0;
+
+    for (i = 1; i <= 100; ++i)
+    {
+        sum1 += i;
+        sum2 += i*i;
+    }
+
+    sum1 *= sum1;
+
+    printf("%ld\n", labs(sum1-sum2));
+
+    return 0;
+}
\ No newline at end of file
diff --git a/p7/CMakeLists.txt b/p7/CMakeLists.txt
new file mode 100644
index 0000000..d7a258f
--- /dev/null
+++ b/p7/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem7 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p7 ${SOURCES})
+TARGET_LINK_LIBRARIES(p7 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p7/main.c b/p7/main.c
new file mode 100644
index 0000000..ef215ed
--- /dev/null
+++ b/p7/main.c
@@ -0,0 +1,11 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+#include "primes_1000000.h"
+
+int main(int argc, char **argv)
+{
+    printf("%ld\n", prime_table[10000]);
+    return 0;
+}
\ No newline at end of file
diff --git a/p8/CMakeLists.txt b/p8/CMakeLists.txt
new file mode 100644
index 0000000..05ab8c7
--- /dev/null
+++ b/p8/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem8 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p8 ${SOURCES})
+TARGET_LINK_LIBRARIES(p8 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p8/main.c b/p8/main.c
new file mode 100644
index 0000000..f671830
--- /dev/null
+++ b/p8/main.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+static const char *thebignumber =
+"73167176531330624919225119674426574742355349194934"
+"96983520312774506326239578318016984801869478851843"
+"85861560789112949495459501737958331952853208805511"
+"12540698747158523863050715693290963295227443043557"
+"66896648950445244523161731856403098711121722383113"
+"62229893423380308135336276614282806444486645238749"
+"30358907296290491560440772390713810515859307960866"
+"70172427121883998797908792274921901699720888093776"
+"65727333001053367881220235421809751254540594752243"
+"52584907711670556013604839586446706324415722155397"
+"53697817977846174064955149290862569321978468622482"
+"83972241375657056057490261407972968652414535100474"
+"82166370484403199890008895243450658541227588666881"
+"16427171479924442928230863465674813919123162824586"
+"17866458359124566529476545682848912883142607690042"
+"24219022671055626321111109370544217506941658960408"
+"07198403850962455444362981230987879927244284909188"
+"84580156166097919133875499200524063689912560717606"
+"05886116467109405077541002256983155200055935729725"
+"71636269561882670428252483600823257530420752963450";
+
+void read_next_digits(int *pos, int *digits, int *zero)
+{
+    int i = 0;
+    for (i = 0; i < 5; ++i)
+    {
+        digits[i] = thebignumber[(*pos)+i] - 48;
+        if (digits[i] == 0)
+            *zero = 1;
+    }
+    *pos += 1;
+}
+
+int product(int *digits)
+{
+    int i, r=1;
+    for (i = 0; i < 5; ++i)
+        r = r * digits[i];
+    return r;
+}
+
+int max(int a, int b)
+{
+    return a < b ? b : a;
+}
+
+int main(int argc, char **argv)
+{
+    int digits[5];
+    int pos = 0;
+    int zero;
+    int prod=0;
+
+    while (pos < 1000)
+    {
+        zero = 0;
+        read_next_digits(&pos, digits, &zero);
+        if (zero)
+            continue;
+        prod = max(product(digits), prod);
+    }
+
+    printf("%d\n", prod);
+
+    return 0;
+}
\ No newline at end of file
diff --git a/p9/CMakeLists.txt b/p9/CMakeLists.txt
new file mode 100644
index 0000000..987dbf1
--- /dev/null
+++ b/p9/CMakeLists.txt
@@ -0,0 +1,7 @@
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+PROJECT(euler_problem9 C)
+INCLUDE_DIRECTORIES(../common)
+SET(SOURCES main.c ../common/utils.c)
+ADD_EXECUTABLE(p9 ${SOURCES})
+TARGET_LINK_LIBRARIES(p9 m)
+SET_SOURCE_FILES_PROPERTIES(${SOURCES} PROPERTIES COMPILE_FLAGS -g)
diff --git a/p9/main.c b/p9/main.c
new file mode 100644
index 0000000..c75fea9
--- /dev/null
+++ b/p9/main.c
@@ -0,0 +1,89 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+int gen(int p, int pmax, int q)
+{
+    int a, b, c;
+
+    for (; p < pmax; p += 2)
+    {
+        int _q = q;
+
+        for (; _q < p; _q += 2)
+        {
+            if (!pythagorean_triplet(p, _q, &a, &b, &c))
+                continue;
+
+            printf("p:%d q:%d a:%d\tb:%d\tc:%d\n", p, _q, a, b, c);
+
+            if (a+b+c == 1000)
+                goto found;
+
+            if (1000 % (a+b+c) == 0)
+            {
+                int m = 1000 / (a+b+c);
+
+                printf("triplet sum (%d) is divisor of 1000, multiply by %d\n",
+                    a+b+c, m);
+
+                a *= m;
+                b *= m;
+                c *= m;
+
+                if (a+b+c == 1000)
+                    goto found;
+            }
+        }
+    }
+
+    return 0;
+
+found:
+
+    printf("got it: a:%d b:%d c:%d a*b*c=%d\n", a, b, c, a*b*c);
+
+    return 1;
+}
+
+int main(int argc, char **argv)
+{
+    // some different ways to generate pythagorean triples, let's hope one of
+    // these yields the result
+
+    if (gen(3, 20, 3))
+        return 0;
+
+    printf("--\n");
+
+    if (gen(3, 20, 2))
+        return 0;
+
+    printf("--\n");
+
+    if (gen(2, 20, 3))
+        return 0;
+
+    // and of course the brute-force way :-) (this could be optimized by
+    // making the condition b<1000 -> b<1000-a and just stating c=1000-a-b
+    // instead of iterating values of c).
+
+    // int a, b, c;
+
+    // for (a = 1; a < 1000; a++)
+    // {
+    //     for (b = a+1; b < 1000; b++)
+    //     {
+    //         for (c = b+1; c < 1000; c++)
+    //         {
+    //             if ((a + b + c == 1000) && (a*a + b*b == c*c))
+    //             {
+    //                 printf("a:%d b:%d c:%d a*b*c:%d\n", a, b, c, a*b*c);
+    //                 return 0;
+    //             }
+    //         }
+    //     }
+    // }
+
+    return 0;
+}
+