Project Euler #1 - Sum of Multiples of 3 or 5

C Solution Walkthrough

1. Problem Statement


• Find the sum of all the natural numbers below N that are multiples of 3 or 5.


• For the original problem, N = 1000.


• Example for a smaller N:
  • Below 10, the multiples of 3 or 5 are 3, 5, 6, 9.
  • Their sum is 3 + 5 + 6 + 9 = 23.



2. My C Solution



#include <stdint.h>
#include <stdio.h>

#ifndef N
#define N (1000ul)
#endif // N

uint64_t solve(uint64_t n)
{
    uint64_t sum = 0;
    for (uint64_t i = 3; i < n; i++)
    {
        if (i % 3 == 0 || i % 5 == 0)
        {
            sum += i;
        }
    }
    return sum;
}

int main()
{
    fprintf(
            stdout,
            "The sum of all the multiples of 3 or 5 below %lu is: %lu\n",
            N,
            solve( N ));
    return 0;
}




3. High-Level Approach


• We want all numbers i such that:
  • 0 < i < N
  • and i is divisible by 3 or 5


• The algorithm you used is straightforward and readable:
1. Start with sum = 0.
2. Loop over all integers i from 3 up to (but not including) N.
3. If i is a multiple of 3 or 5, add it to sum.
4. At the end, return sum.


• This is an O(N) solution: it checks each integer once.



4. Header Files and Types



#include <stdint.h>
#include <stdio.h>



• <stdint.h> is included so you can use fixed-width integer types like uint64_t.


• <stdio.h> is needed for fprintf and stdout in main.


• Using uint64_t for the sum is a defensive choice:
  • It's a 64-bit unsigned integer — very large range before overflow.
  • Even if you increased N (for other experiments), your sum is unlikely to overflow quickly.



5. The N macro (configurable limit)



#ifndef N
#define N (1000ul)
#endif // N



• This allows N to be defined at compile-time (for example via -DN=2000), while still having a default.


• If N is not already defined, it defaults to 1000ul:
  • 1000ul → unsigned long literal.
  • Good match for the %lu format specifier in fprintf.


• So you can compile like:

gcc -DN=5000 euler1.c -o euler1
./euler1



• Now the program will compute the sum below 5000 instead of 1000, without changing the source code.



6. The solve Function



uint64_t solve(uint64_t n)
{
    uint64_t sum = 0;
    for (uint64_t i = 3; i < n; i++)
    {
        if (i % 3 == 0 || i % 5 == 0)
        {
            sum += i;
        }
    }
    return sum;
}



• uint64_t solve(uint64_t n):
  • The function takes a single parameter n — the exclusive upper bound.
  • It returns the total sum as a 64-bit unsigned integer.


• uint64_t sum = 0;:
  • Initializes the running total.


• The for loop:

  for (uint64_t i = 3; i < n; i++)
  

  • Starts i at 3 because 1 and 2 are not multiples of 3 or 5 (you could also start from 1, but this is a tiny micro-optimization).
  • Runs while i < n, so n itself is not included — which exactly matches "below n".


• The condition:

  if (i % 3 == 0 || i % 5 == 0)
  

  • i % 3 == 0 → i is divisible by 3.
  • i % 5 == 0 → i is divisible by 5.
  • The logical OR || means if either is true, the number counts.
  • This automatically handles numbers like 15 which are multiples of both 3 and 5 — they are still added only once because the condition is just a yes/no test.


• Accumulating into sum:

  sum += i;
  

  • Each qualifying i is added to the running total.


• Finally:

  return sum;
  

  • After finishing the loop, the function returns the total sum of all such multiples.



7. The main Function



int main()
{
    fprintf(
            stdout,
            "The sum of all the multiples of 3 or 5 below %lu is: %lu\n",
            N,
            solve( N ));
    return 0;
}



• solve(N) calls your function with the compile-time constant N.


• fprintf(stdout, ...) prints the result to standard output:
  • %lu is used twice for printing unsigned long values (for N and the result).
  • This matches 1000ul as the default N.


• The output is a friendly sentence:

  
  The sum of all the multiples of 3 or 5 below 1000 is: 233168
  



• return 0; indicates successful program termination.



8. Complexity and Performance


• The loop runs once for every integer i from 3 to n-1.


• Time complexity: O(n).


• Space complexity: O(1) — only a few integer variables.


• For n = 1000, this is extremely fast. Even for quite large n, this approach is fine in C.

Haskell Solution Walkthrough

1. Problem Statement


• Same as before.



2. The Full Haskell Solution

main :: IO ()
main = print $ sum [x | x <- [1 .. 999], x `mod` 3 == 0 || x `mod` 5 == 0]



• This is a compact but fully functional Haskell program — no helper functions required.
• We'll now break it down line by line to understand every part.



3. The Type Signature

main :: IO ()



• In Haskell, every program must have a main function of type IO ().


• This means it performs side effects (printing to the console) but doesn't return a value in the pure sense — the empty parentheses () mean "no meaningful value."


• All computation inside main must therefore be expressed as an IO action.



4. The Body of main

main = print $ sum [x | x <- [1 .. 999], x `mod` 3 == 0 || x `mod` 5 == 0]



• This line combines three main concepts in idiomatic Haskell:
  1. List comprehension — to build the list of all numbers divisible by 3 or 5.
  2. sum — a built-in higher-order function that adds all elements in a list.
  3. print — an I/O action that displays the result.



5. List Comprehension

[x | x <- [1 .. 999], x `mod` 3 == 0 || x `mod` 5 == 0]



• This is Haskell's list comprehension syntax, inspired by mathematical set notation.


• It can be read as:

  "The list of all x taken from [1..999], such that x is divisible by 3 or 5."



• Breaking it down:
  • [1 .. 999] → Generates all integers from 1 to 999 (inclusive).
  • x <- [1 .. 999] → Means "take each x from that list."
  • x `mod` 3 == 0 || x `mod` 5 == 0 → The filtering condition.


• So only numbers satisfying the condition remain in the resulting list.



6. Using sum

sum [x | x <- [1 .. 999], x `mod` 3 == 0 || x `mod` 5 == 0]



• sum is a built-in Haskell function that adds up all elements in a list of numbers.


• Type signature (simplified):

  sum :: (Num a) => [a] -> a
  

• It takes a list of numbers and returns their total.


• Here, [x | ...] produces a list like [3,5,6,9,10,12,...,999], and sum adds them together.



7. Printing the Result

print $ sum [...]



• print is a standard I/O function in Haskell that converts a value to a string and writes it to standard output.


• Type signature:

  print :: Show a => a -> IO ()
  



• The $ operator is just syntactic sugar for parentheses:
  • print $ sum [ ... ] = print (sum [ ... ])


• The whole expression produces an IO () action — suitable for main.



8. Putting It All Together


• The evaluation steps conceptually look like this:

-- Step 1: Generate the list
[x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
-- => [3,5,6,9,10,12,15,18,20,...,999]

-- Step 2: Sum the list
sum [3,5,6,9,10,12,15,...,999]
-- => 233168

-- Step 3: Print the result
print 233168



• Haskell lazily generates and sums the list; memory use stays small because it doesn't keep the entire list in memory at once — elements are processed as needed.



9. Performance Consideration


• This is an O(n) approach: it checks every number up to 999 once.


• For such a small range, this is trivial and effectively instantaneous.


• Like the C version, you could also use a mathematical shortcut with arithmetic series, but Haskell's concise syntax makes even the direct version perfectly fine.



10. Alternative: Using Higher-Order Functions

main :: IO ()
main = print . sum . filter f $ [1..999]
  where f x = x `mod` 3 == 0 || x `mod` 5 == 0



• This version uses filter and function composition (.) instead of list comprehension.
• Both are equivalent; the choice is stylistic.
• Haskell programmers often prefer whichever feels more readable in context.