用 Python 编写程序，查找给定数组中每对都是好数的任意序列的最大大小

假设我们有一个大小为 n 的序列 nums。我们必须找到 nums 子序列的最大大小，其中每对 (p, q) 都是好数?当且仅当满足以下至少一个条件时，才称一对是好数:1. p 的不同素因数的数量的奇偶性等于 b 的不同素因数的数量的奇偶性。例如，值 18 有两个不同的素因数:2 和 3。2. p 的所有正因数之和的奇偶性与 q 相同。

因此，如果输入为 nums = [2,3,6,8]，则输出将为 3

为了解决这个问题，我们将遵循以下步骤 −

• n := size of nums
• 定义三个空列表 cnt、total、result
• 对于 nums 中的每个 i，执行
  • 计数:= 0, tot := 0
  • prime := a new list
  • 对于 nums 中的每个 j，执行
    • 如果 (j mod k 对所有在 2 到 j 范围内的 k) 为真，则
      • 在 prime 的末尾插入 j
  • 对于 prime 中的每个 j，执行
    • 如果 i mod j 为 0，则
      • count := count + 1
  • 如果 count 为偶数，则
    • 插入"奇数"在 cnt 的末尾
  • 否则，
    • 在 cnt 的末尾插入 'even'
    • 对于 j 在 1 到 i 的范围内，执行
      • 如果 i mod j 等于 0，则
        • tot := tot + j
    • 如果 tot 为奇数，则
      • 在 total 的末尾插入 'odd'
    • 否则，
      • 插入 'even'在 total 的末尾
  • 对于范围在 0 到 n-2 内的 i，执行
    • 对于范围在 i+1 到 n - 1 内的 j，执行
      • 如果 cnt[i] 与 cnt[j] 相同或 total[i] 与 total[j] 相同，则
        • 在 result 的末尾插入 nums[i]
        • 如果 j 与 n-2 相同，则
          • 在 result 的末尾插入 nums[j]
    • result := 来自 result 的新集合的新列表
    • 返回 result 的大小

    示例

    让我们看看下面的实现以便更好地理解 −

    def solve(nums):
       n = len(nums)
       cnt = []
       total = []
       result = []
       for i in nums:
          count = 0
          tot = 0
    
          prime = []
          for j in nums:
             if all(j % k for k in range(2, j)) == True:
                prime.append(j)
    
          for j in prime:
             if i % j == 0:
                count += 1
          if count % 2:
             cnt.append('odd')
          else:
             cnt.append('even')
    
          for j in range(1,i+1):
             if i % j == 0:
                tot += j
    
          if tot % 2:
             total.append('odd')
          else:
             total.append('even')
    
       for i in range(n-1):
          for j in range(i+1, n):
    
             if cnt[i] == cnt[j] or total[i] == total[j]:
                result.append(nums[i])
    
                if j == n-1:
                   result.append(nums[j])
    
       result = list(set(result))
       return len(result)
    
    nums = [2,3,6,8]
    print(solve(nums))
    

    输入

    15, 3, 8
    

    输出

    3
    

    ---

    相关文章

    • Python 中元组列表到字典的转换
    • Python - 从两个列表中配对，使得成对的元素不相同
    • 使用 Python 和 SQLite 的 SQL
    • 使用 pytrie 模块在 Python 中进行前缀匹配
    • 创建和访问 Python 包
    • 如何使用正则表达式和数据类型选择多个 DataFrame 列
    • 如何在 Pandas 中查找和过滤重复行?
    • 用 Python 编写程序以正确的顺序查找机场?
    • 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
    • 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

    ---

    有用资源

    • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

    ---

    打印 下一节:用 Python 编写程序来查找两个矩形覆盖的总面积 ❯❮ 上一节:在 Python 中通过连接 n 次来查找数字模数的程序