基础算法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n-2):
            x = nums[i]
            if x + nums[i+1] + nums[i+2] > 0:
                break
            if nums[n-1] + nums[n-2] + nums[n-3] < 0:
                break
            if x + nums[n-1] + nums[n-2] < 0:
                continue
            if i > 0 and x == nums[i-1]:
                continue
            j = i+1
            k = n-1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s > 0:
                    k -=1
                elif s < 0:
                    j +=1
                else:
                    ans.append([nums[i],nums[j],nums[k]])
                    j = j+1
                    while j < k and nums[j] == nums[j-1]:
                        j = j+1
                    k = k-1
                    while j < k and nums[k] == nums[k+1]:
                        k = k-1
        return ans 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        '''
        1.
        '''
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
           s = (right - left) * (min(height[left],height[right]))
           ans = max(ans,s)
           if height[left] < height[right]:
            left += 1
           else:
            right -= 1
        return ans

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        pre_max = [0] * n
        aft_max = [0] * n
        pre_max[0] = height[0]
        aft_max[-1] = height[-1]
        ans = 0
        for i in range(1,len(height)):
            max_num = max(pre_max[i-1],height[i])
            pre_max[i] = max_num
        for j in range(len(height)-2,-1,-1):
            max_num = max(aft_max[j+1],height[j])
            aft_max[j] = max_num
        for k,pre,aft in zip(height,pre_max,aft_max):
            min_num = min(pre,aft)
            ans += (min_num - k)
        return ans 

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left = 0
        right = n - 1
        pre_max = 0
        aft_max = 0
        ans = 0
        while left <= right:
            pre_max = max(pre_max,height[left])
            aft_max = max(aft_max,height[right])
            if pre_max < aft_max:
                ans += pre_max - height[left]
                left += 1
            else:
                ans += aft_max - height[right]
                right -= 1
        return ans 
        

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s = 0
        left = 0
        for right,x in enumerate(nums):
            s += x
            while s >= target:
                ans = min(ans,right - left + 1)
                s -= nums[left]
                left += 1
        return ans if ans <= n else 0 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        cut = Counter()
        left = 0
        for right,x in enumerate(s):
            cut[x] += 1
            while cut[x] > 1:
                cut[s[left]] -= 1
                left += 1
            ans = max(ans,right - left + 1)
        return ans

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        ans = 0
        s = 1
        left = 0
        for right,x in enumerate(nums):
            s *= x
            while s >= k:
                s //= nums[left]
                left += 1
            ans += right - left + 1
        return ans  
        

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    # 闭区间写法
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间 [left, right]
        while left <= right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1  # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right]
        # 循环结束后 left = right+1
        # 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    # 左闭右开区间写法
    def lower_bound1(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 左闭右开区间 [left, right)
        while left < right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid  # 范围缩小到 [left, mid)
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right)
        # 循环结束后 left = right
        # 此时 nums[left-1] < target 而 nums[left] = nums[right] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    
    # 开区间写法
    def lower_bound2(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums)  # 开区间 (left, right)
        while left + 1 < right:  # 区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[left] < target
            # nums[right] >= target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        # 循环结束后 left+1 = right
        # 此时 nums[left] < target 而 nums[right] >= target
        # 所以 right 就是第一个 >= target 的元素下标
        return right

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

# 写法一：求前缀和
from itertools import accumulate
def get_sum(a):
  sum = list(accumulate(a))
  return sum
# 写法二：求前缀和
def get_presum(a):
    n = len(a)
    sum = [0] * n
    sum[0] = a[0]
    for i in range(1,n):
        sum[i] = sum[i-1] +a[i]
    return sum

# 快速求区间和
def get_sum(sum,l,r):
    if l == 0:
        return sum[r]
    else:
        return sum[r] - sum[l-1]

a = [1,2,3,4,5]
sum = get_presum(a)
print(sum) #[1, 3, 6, 10, 15]
he = get_sum(sum,3,4)
print(he) #9

# coding:utf-8
# @Time: 2025/4/6 11:27
# @Author: liuyu

import os
import sys

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
n,m,q = map(int,input().split())
a = [[0] * (m+1) for _ in range(n+1)]
qian_a = [[0] * (m+1) for _ in range(n+1)]
def qiuhe(a):
    for x in range(1,n+1):
        for y in range(1,m+1):
            if x == 1 and y == 1:
                qian_a[x][y] = a[x][y]
            else:
                qian_a[x][y] = qian_a[x-1][y] + qian_a[x][y-1] - qian_a[x-1][y-1] + a[x][y]

for i in range(1,n+1):
    a[i] = [0] + list(map(int,input().split()))
qiuhe(a)
for _ in range(q):
    x1,y1,x2,y2 = map(int,input().split())
    sum_a = qian_a[x2][y2] - qian_a[x1-1][y2] - qian_a[x2][y1-1] + qian_a[x1-1][y1-1]
    print(sum_a)

import sys
input = lambda: sys.stdin.readline().strip()
while True:
    try:
        n,m = map(int,input().split())
        a = list(map(int,input().split()))
        # *******核心部分*********
        # 构建差分数组
        dif = [0] * (n + 1)
        dif[0] = a[0]
        for i in range(1,n):
            dif[i] = a[i] - a[i-1]
        # 区间求和转化成差分数组
        for j in range(m):
            x,y,z = map(int,input().split())
            x -= 1
            y -= 1
            dif[x] += z
            dif[y + 1] -= z
        # 对差分数组求前缀和
        a[0] = dif[0]
        # 写法1
        # for k in range(1,n):
        #     for h in range(0,k+1):
        #         a[k] += dif[h]
        # 写法2
        for k in range(1, n):
            a[k] = dif[k] + a[k - 1]
        # *******核心部分*********
        print(" ".join(map(str,a)))

    except:
        break

input = lambda: sys.stdin.readline().strip()
n,m = map(int,input().split())
qipan = [[0] * (n+1) for _ in range(n+1)]
diff = [[0] * (n+2) for _ in range(n+2)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if i == 1 and j == 1:
            diff[i][j] = qipan[i][j]
        else:
            diff[i][j] = qipan[i][j] - qipan[i-1][j] - qipan[i][j-1] + qipan[i-1][j-1]
for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    diff[x1][y1] += 1
    diff[x1][y2+1] -= 1
    diff[x2+1][y1] -= 1
    diff[x2+1][y2+1] += 1

for i in range(1,n+1):
    for j in range(1,n+1):
        if i == 1 and j == 1:
            qipan[i][j] = diff[i][j]
        else:
            qipan[i][j] = qipan[i - 1][j] + qipan[i][j - 1] - qipan[i - 1][j - 1] + diff[i][j]

import sys
input = lambda : sys.stdin.readline().strip()
n = int(input())
a = list(map(int, input().split()))

for i in range(1,n):
    for j in range(0,n-i):
        if a[j+1] < a[j]:
            a[j],a[j+1] = a[j+1],a[j]
print(a)

import sys

input = lambda: sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
# 把列表分为三部分
def parttation(a,left,right):
    temp = left + 1
    for i in range(left+1,right):
        if a[left] > a[i]:
            a[i],a[temp] = a[temp],a[i]
            temp += 1
    a[left],a[temp-1] = a[temp-1],a[left]
    return temp - 1

# 快速排序
def quickly(a,left,right):
    if left < right:
        mid = parttation(a,left,right)
        quickly(a,left,mid)
        quickly(a,mid+1,right)

quickly(a,0,n)
print(a)

import sys

input = lambda: sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
# 两个有序列表合并
def merge(A,B):
    result = []
    while len(A) != 0 and len(B) != 0:
        if A[0] < B[0]:
            result.append(A.pop(0))
        else:
            result.append(B.pop(0))
    result.extend(A)
    result.extend(B)
    return result
# 归并排序
def sort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    left = sort(a[:mid])
    right = sort(a[mid:])
    return merge(left,right)

print(sort(a))

def tong_sort(a,bucketcount):
    """
    :param a: 排序列表
    :param bucketcount: 桶的数量
    :return:
    """
    minvalue,maxvalue = min(a),max(a)
    # 每个桶的大小，元素范围
    bucketsize = (maxvalue - minvalue + 1) // bucketcount
    res = [[] for i in range(bucketcount+1)]
    for x in a:
        idx = (x - minvalue) // bucketsize
        res[idx].append(x)
    ans = []
    # 对每个桶中的元素排序
    for x in res:
        x.sort()
        ans.extend(x)
    return ans

a = [1,6,3,5,8,2,1]
res = tong_sort(a,min(1000,len(a)))
print(res)

import sys
import heapq

input = lambda: sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
# 建一个堆
heapq.heapify(a)
ans = 0
while len(a) != 1:
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    heapq.heappush(a,x+y)
    ans += (x+y)
print(ans)

import os
import sys

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
w = int(input())
n = int(input())
a = []
for i in range(n):
  p = int(input())
  a.append(p)

a.sort()
l = 0
r = n-1
ans = 0
while True:
  if l == r:
    ans += 1
    break
  if l > r:
    break
  if a[l] + a[r] <= w:
    l += 1
    r -= 1
    ans += 1
  else:
    r -= 1
    ans += 1
print(ans)

def dfs(depth):
    """
    depth:当前为第几重循环
    """
    if depth == n:
        # n重循环最内层执行的代码
        return
    # 每次循环进行的枚举选择

import sys
input = lambda: sys.stdin.readline().strip()
x,n = map(int,input().split())
# 记录每层选择的数字
a = [0] * n
# 统计有几种方案
count = 0
def dfs(deepth):
    if deepth == n:
        # 条件一：数字需要递增
        for j in range(0,n-1):
            if a[j+1] >= a[j]:
                continue
        # 条件二：数字和为x
        sum = 0
        for k in range(n):
            sum += a[k]
        if sum == x:
            global count
            count += 1
            print(a)
        return
    # 第deepth层进行选择数字
    for i in range(1,x+1):
        # 选择第deepth层的数字
        a[deepth] = i
        # 递归进行下一层   
        dfs(deepth+1)

dfs(0)
print(count)

import sys
n = 7
ans = 0
temp = [[0,0] for i in range(7)]

def dfs(deepth):
    if deepth == n:
        sum1 = 0
        sum2 = 0
        for x in range(n):
            sum1 += temp[x][0]
            sum2 += temp[x][1]
        if sum1 == 9 and sum2 == 16:
            global ans
            ans += 1
        return
    for i in range(0,6):
        for j in range(0,6):
            if 2<= i+j<=5:
                temp[deepth][0] = i
                temp[deepth][1] = j
                dfs(deepth+1)

dfs(0)
print(ans)

# 该题解只能解决65%的评测用例
import sys
input = lambda: sys.stdin.readline().strip()
n,m = map(int,input().split())
m = m * 2 #x2避免m除以2有小数
a = list(map(int,input().split()))
a = [x * 2 for x in a] #mx2，那么每个瓜的重量也x2
ans = n +1
def dfs(deepth,wight,count):
    # wight:当前买到的瓜的重量
    # count:当前劈的次数
    if wight > m:
        return
    if wight == m:
        global ans
        ans = min(ans,count)
    if deepth == n:
        return
    # 买一个西瓜
    dfs(deepth+1,wight + a[deepth],count)
    # 买半个西瓜
    dfs(deepth+1,wight + a[deepth] // 2,count+1)
    # 不买西瓜
    dfs(deepth+1,wight,count)

dfs(0,0,0)
if ans == n+1:
    ans = -1
print(ans)

import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
ans = 0
vis1 = [False] * (n+1)
vis2 = [False] * (2 * n+1)
vis3 = [False] * (2 * n+1)
def dfs(x):
    # 当前为第x行，1到x-1行已经设置好
    if x == n+1:
        global ans
        ans += 1
        return
    # 枚举第x行放在哪列 
    for y in range(1,n+1):
        if vis1[y]  or vis2[x+y] or vis3[x-y+n]:
            continue
        # 标记当前状态
        vis1[y]  = vis2[x+y] = vis3[x-y+n] = True
        dfs(x+1)
        # 删除标记
        vis1[y]  = vis2[x+y] = vis3[x-y+n] = False

dfs(1)
print(ans)

import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(100000)
N = int(input())
a = [0] + list(map(int, input().split()))
# 记录走的步长
vits = [0] * (N + 1)
ans = 0
def dfs(x,length):
    # 记录当前走的步长
    vits[x] = length
    # 看接下来要走的之前是否走过
    if vits[a[x]] != 0:
        global ans
        ans = max(ans,length - vits[a[x]] + 1)
    else:
        dfs(a[x],length+1)

for i in range(1,N+1):
    if vits[i] == 0:
        dfs(i,1)

print(ans)

import os
import sys
sys.setrecursionlimit(100000)
# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
n = int(input())
MAP = []
vits = []
ans = 0
for i in range(n):
  MAP.append(list(input()))
  vits.append([0] * n)

def dfs(x,y):
  # 标记当前点 
  vits[x][y] = 1
  # 判断当前点是否为高地
  if MAP[x][y-1] == "#" and MAP[x][y+1] == "#" and MAP[x-1][y] == "#" and MAP[x+1][y] == "#":
    global flag
    flag = True
  # 把四周未遍历的土地继续遍历
  for dir_x,dir_y in ([0,-1],[0,1],[-1,0],[1,0]):
    xx = x + dir_x
    yy = y + dir_y
    if MAP[xx][yy] == "#" and vits[xx][yy] == 0:
          dfs(xx,yy)

for x in range(n):
  for y in range(n):
    if MAP[x][y] == "#" and vits[x][y] == 0:
      flag = False
      dfs(x,y)
      if flag == False:
        ans += 1
print(ans)

import os
import sys

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
Group = []
ans = n

def check(depth,group):
  for i in group:
    if depth % i == 0 or i % depth == 0:
      return False
  return True

def dfs(depth):
  # depth：表示当前第几个学生
  global ans
  if len(Group) > ans:
    return

  if depth == n:
    ans = min(ans,len(Group))
    return
  # 判断当前学生可以加入哪个组
  for every_group in Group:
    if check(a[depth],every_group):
      every_group.append(a[depth])
      dfs(depth + 1)
      every_group.pop()
  
  # 学生也可以单独为一组
  Group.append([a[depth]])
  dfs(depth + 1)
  Group.pop()

dfs(0)
print(ans)

import os
import sys

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
t,n = map(int,input().split())
path = []
ans = [0] * 1000001

def dfs(depth,val_lastline,total,cj):
  # depth:代表第n条边
  # val_lastline:代表上一条边的边长
  # total：代表当前的总边长
  # cj：代表当前n边形的值
  if depth == n:
    if total > 2 * path[-1]:
      ans[cj] += 1
    return
  for i in range(val_lastline+1,100000):
    # 已经有depth条边了，后续还有n - depth条边，累计乘积要不超过 cj * (i ** (n - depth))
    if cj * (i ** (n - depth)) <= 100000:
      path.append(i)
      dfs(depth+1,i,total + i,cj * i)
      path.pop()
    else:
      break
dfs(0,0,0,1)
# 求前缀和
for i in range(1,len(ans)):
  ans[i] += ans[i-1]
for _ in range(t):
  l,r = map(int,input().split())
  print(ans[r] - ans[l-1])

# 原始
def dfs(x):
    if x == 0 or x == 1:
        return 1
    return f(x-1) + f(x-2)

# 记忆化1
dic = {0:1,1:1}
def dfs(x):
    if x in dic.keys():
        return dic[x]
    dic[x] = f(x-1) + f(x-2)
    return dic[x]

# 记忆化2 python使用这个
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x):
    if x == 0 or x == 1:
        return 1
    return f(x-1) + f(x-2)

import os
import sys
from functools import lru_cache 

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
n,m,k = map(int,input().split())
A,B,C,D = map(int,input().split())
A -= 1
B -= 1
C -= 1
D -= 1
MAP = []
for i in range(n):
  MAP.append(list(map(int,input().split())))
@lru_cache(maxsize=None)
def dfs(x,y,z):
  if x == C and y == D:
    return True
  for dir_x,dir_y in [(0,1),(1,0),(-1,0),(0,-1)]:
    xx,yy = dir_x + x,dir_y + y
    if 0 <= xx < n and 0 <= yy < m:
      if MAP[xx][yy] < MAP[x][y]:
        if dfs(xx,yy,z):
          return True
      elif z == False and MAP[x][y] + k > MAP[xx][yy]:
        if dfs(xx,yy,True):
          return True
    else:
      continue

if dfs(A,B,False):
  print("Yes")
else:
  print("No")  

import os
import sys
from functools import lru_cache 

# 请在此输入您的代码
input = lambda: sys.stdin.readline().strip()
n,m,k = map(int,input().split())
MAP = []
for i in range(n):
  MAP.append(list(map(int,input().split())))
@lru_cache(maxsize=None)
def dfs(x,y,z,w):
  # x,y代表当前位置
  # z代表当前宝贝的件数
  # w代表当前得到的宝贝中价值最大的
  if x == n - 1 and y == m - 1:
    # 当前不需要选择
    if z == k:
      return 1
    # 当前需要选择
    if z == k - 1 and MAP[x][y] > w:
      return 1
    return 0
  ans = 0
  for dir_x,dir_y in [(0,1),(1,0)]:
    xx,yy = x + dir_x,y + dir_y
    if xx < n and yy < m:
      # 不拿宝贝
      ans += dfs(xx,yy,z,w)
      # 拿宝贝
      if MAP[x][y] > w:
        ans += dfs(xx,yy,z+1,MAP[x][y])
    else:
      continue
  return ans % 1000000007
print(dfs(0,0,0,-1))

Next = [0] * (1000010)
def get_next(t):
    for i in range(1,len(t)):
        j = Next[i]
        while j > 0 and t[i] != t[j]:
            j = Next(j)
        if t[i] == t[j]:
            Next[i+1] = j + 1
        else:
            Next[i+1] = 0

# 返回s中t出现的次数
def KMP(s,t):
    ans = 0
    j = 0
    get_next(t)
    for i in range(len(s)):
        # 如果s[i]和t[j]不匹配，则j=Next[j]
        while j > 0 and s[i] != t[j]:
            j = Next[j]
        # 判断是否匹配
        if s[i] == t[j]:
            j += 1
        # 判断是否匹配完，匹配完全则记录答案
        if j == len(t):
            ans += 1
            j = Next[j]
    return ans

B = 26
mod = 1000000007
def Hash(s):
    res = 0
    for c in s:
        res = res * B + ord(c) - ord('A')
        res %= mod
    return res

t = input()
s = input()
m,n = len(t),len(s),
numT = Hash(t)
hash = [0]
for c in s:
    hash.append((hash[-1] * B + ord(c) -ord('A')) % mod)
ans = 0
p = (B ** m) % mod
# 枚举所有区间[l,l+m-1]
for l in range(1,n+1):
    r = l + m - 1
    if r > n:
        break
    if (hash[r] - hash[l-1] * p % mod +mod)%mod == numT:
        ans += 1
print(ans)

import sys
input = lambda:sys.stdin.readline().strip()

def Findroot(x):
    if x == p[x]:
        return x
    p[x] = Findroot(p[x])
    return p[x]

def Merge(x,y):
    rootx,rooty = Findroot(x),Findroot(y)
    p[rootx] = rooty

def Query(x,y):
    rootx,rooty = Findroot(x),Findroot(y)
    return rootx == rooty

n,m = map(int,input().split())
p = list(range(n+1))
for _ in range(m):
    op,x,y = map(int,input().split())
    if op == 1:
        Merge(x,y)
    else:
        if Query(x,y):
            print("YES")
        else:
            print("NO")

import sys
input = lambda: sys.stdin.readline().strip()
n,m = map(int,input().split())
a = list(map(int,input().split()))
dfs = [0] * (n + 1)
vit = [0] * (n + 1)
for i in a:
    vit[i] = 1
dfs[0] = 1
dfs[1] = 1 - vit[1]
for i in range(2,n+1):
    if vit[i] == 1:
        continue
    dfs[i] = (dfs[i-1] + dfs[i-2]) % 1000000007
print(dfs[n])

import os
import sys

# 请在此输入您的代码

MOD = 1000000007
n, k = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1,n+1):
  if i - k - 1 >= 0:
    dp[i] = (dp[i-1] + dp[i-k-1]) % MOD
  else:
    dp[i] = (dp[i-1] + 1) % MOD
print(dp[n])

def is_zhishu(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def func(n):
    isprime = [True] * (n + 1)
    # 0 和 1 不是素数
    isprime[0] = isprime[1] = False
    result = []
    for i in range(2, n + 1):
        # 如果当前数字是素数
        if isprime[i]:
            result.append(i)
            # 对于素数 i，将其所有大于 i 的倍数标记为非素数。
            # 这一步的核心思想是：如果一个数是某个素数的倍数，那么它一定不是素数。
            for j in range(i * 2, n, i):
                isprime[j] = False
    return result

def find_composites(n):
    isprime = [True] * (n + 1)  # 初始化布尔数组，默认假设所有数字都是素数
    isprime[0] = isprime[1] = False  # 0 和 1 不是素数也不是合数
    composites = []  # 存储合数的结果

    for i in range(2, n + 1):
        if isprime[i]:  # 如果 i 是素数
            # 将 i 的倍数标记为非素数（即合数）
            for j in range(i * 2, n + 1, i):
                if isprime[j]:  # 如果 j 尚未被标记为合数
                    isprime[j] = False
                    composites.append(j)  # 收集合数

    return composites