本题是2023年10月17日每日一题
给你一个正整数 n
,请你计算在 [1,n]
范围内能被 3
、5
、7
整除的所有整数之和。
返回一个整数,用于表示给定范围内所有满足约束条件的数字之和。
首先就想到的是暴力枚举了,直接初始化一个sums=0 ,然后从1开始枚举到n,看每一个数据是否能被3,5,7中的任意一个整除,能就累加到sums。
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
for i in range(1,n+1):
if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
sums += i
return sums
这个时候发现运行时间很长。
再小优化一下,让i从3开始遍历,因为小于3的数不可能被整除:
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
i = 3
while i >= n:
if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
sums += i
i += 1
return sums
由于求的是1~n的累加和,所以我们直接把从1~n关于3,5,7的倍数加起来,但是要注意去掉重复的最小公倍数,如15,21,等等。
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
i = 3
while i <= n:
sums += i
i += 3
j = 5
while j <= n:
if j % 3 == 0:
# 重复则去重
j += 5
continue
sums += j
j += 5
k = 7
while k <= n:
if k % 3 == 0 or k % 5 == 0:
# 同上,重复则去重
k += 7
continue
sums += k
k += 7
return sums
还有一种数学思路解题,但不涉及编程,所以直接略过。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。