解题思路

这是一个无倍数数查找问题。关键点如下:

  1. 给定 个互不相同的正整数
  2. 需要找出所有的无倍数数(一个数是无倍数数,当且仅当其他数都不是它的倍数)
  3. 按升序输出所有无倍数数

解题思路:

  1. 首先存储所有正整数
  2. 对于每个数,检查其他数是否是它的倍数
  3. 如果没有其他数是它的倍数,则它是无倍数数
  4. 最后对结果进行排序并输出

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 存储输入的数
    vector<int> nums;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) nums.push_back(x);
    }
    
    // 找出无倍数数
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        bool isNoMultiple = true;
        for (int j = 0; j < nums.size(); j++) {
            if (i != j && (nums[j] % nums[i] == 0)) {
                isNoMultiple = false;
                break;
            }
        }
        if (isNoMultiple) {
            result.push_back(nums[i]);
        }
    }
    
    // 排序并输出
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 存储输入的数
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x > 0) nums.add(x);
        }
        
        // 找出无倍数数
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            boolean isNoMultiple = true;
            for (int j = 0; j < nums.size(); j++) {
                if (i != j && nums.get(j) % nums.get(i) == 0) {
                    isNoMultiple = false;
                    break;
                }
            }
            if (isNoMultiple) {
                result.add(nums.get(i));
            }
        }
        
        // 排序并输出
        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if (i < result.size() - 1) System.out.print(" ");
        }
        System.out.println();
    }
}
n = int(input())
nums = [int(x) for x in input().split() if int(x) > 0]

# 找出无倍数数
result = []
for i in range(len(nums)):
    is_no_multiple = True
    for j in range(len(nums)):
        if i != j and nums[j] % nums[i] == 0:
            is_no_multiple = False
            break
    if is_no_multiple:
        result.append(nums[i])

# 排序并输出
result.sort()
print(" ".join(map(str, result)))

算法及复杂度

  • 算法:暴力枚举
  • 时间复杂度: - 需要对每个数检查其他所有数
  • 空间复杂度: - 需要存储输入数组和结果数组