PE0001: Multiples of 3 and 5 | Zhen Lu – Zhen Lu

Author

Published

Monday, March 31, 2025

题目

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6, 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

问题描述

题目要求：找出所有小于1000的自然数中，3或5的倍数的总和。例如，小于10的符合条件的数有3、5、6、9，它们的和为23。

解答

暴力遍历法（适合小数据）

思路：遍历1到999的所有数，逐个检查是否为3或5的倍数，累加符合条件的数。

# Solution to Project Euler Problem 1
def sum_of_multiples(limit):
    return sum(x for x in range(limit) if x % 3 == 0 or x % 5 == 0)

result = sum_of_multiples(10)
result
result = sum_of_multiples(1000)
result

优点：简单直观，适合编程新手。缺点：当数据量极大（如十亿）时，遍历耗时极长。

方法二：数学公式法

思路：利用等差数列求和公式，避免重复计算。分别计算3、5的倍数总和，减去15的倍数总和（因为15的倍数被重复计算了两次）。

# solution using a more efficient method
def SumDivisibleBy(n, limit) -> int:
    """
    Returns the sum of all numbers less than limit that are divisible by n.
    """
    # Find the largest number less than limit that is divisible by n
    p = (limit - 1) // n
    # Use the formula for the sum of an arithmetic series to calculate the sum
    return n * p * (p + 1) // 2

SumDivisibleBy(3, 10) + SumDivisibleBy(5, 10) - SumDivisibleBy(15, 10)
SumDivisibleBy(3, 1000) + SumDivisibleBy(5, 1000) - SumDivisibleBy(15, 1000)

优点：时间复杂度仅为 O(1)，十亿级数据也能秒出结果。

答案

答案为233168。

---
title: "PE0001: Multiples of 3 and 5"
date: 2025-03-31
description: "Project Euler Problem 1: Multiples of 3 and 5"
image: "https://cdn.jsdelivr.net/gh/Leslie-Lu/WeChatOfficialAccount/img_2025/20250331154617.png"
categories:
  - python
  - project euler
  - algorithm
  - math
  - programming
format:
  html: 
    shift-heading-level-by: 1
    include-in-header:
      - text: |
          <style type="text/css">
          hr.dinkus {
              width: 50px;
              margin: 2em auto 2em;
              border-top: 5px dotted #454545;
          }
          
          div.column-margin+hr.dinkus {
              margin: 1em auto 2em;
          }
          </style>
---

## 题目

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6, 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

## 问题描述

题目要求：找出所有小于1000的自然数中，3或5的倍数的总和。
例如，小于10的符合条件的数有3、5、6、9，它们的和为23。

## 解答

### 暴力遍历法（适合小数据）

思路：遍历1到999的所有数，逐个检查是否为3或5的倍数，累加符合条件的数。

```{python}
# Solution to Project Euler Problem 1
def sum_of_multiples(limit):
    return sum(x for x in range(limit) if x % 3 == 0 or x % 5 == 0)

result = sum_of_multiples(10)
result
result = sum_of_multiples(1000)
result
```

优点：简单直观，适合编程新手。
缺点：当数据量极大（如十亿）时，遍历耗时极长。

### 方法二：数学公式法

思路：利用等差数列求和公式，避免重复计算。分别计算3、5的倍数总和，减去15的倍数总和（因为15的倍数被重复计算了两次）。


```{python}
# solution using a more efficient method
def SumDivisibleBy(n, limit) -> int:
    """
    Returns the sum of all numbers less than limit that are divisible by n.
    """
    # Find the largest number less than limit that is divisible by n
    p = (limit - 1) // n
    # Use the formula for the sum of an arithmetic series to calculate the sum
    return n * p * (p + 1) // 2

SumDivisibleBy(3, 10) + SumDivisibleBy(5, 10) - SumDivisibleBy(15, 10)
SumDivisibleBy(3, 1000) + SumDivisibleBy(5, 1000) - SumDivisibleBy(15, 1000)
```

优点：时间复杂度仅为 `O(1)`，十亿级数据也能秒出结果。

## 答案

答案为233168。