首页 > 试题广场 >

无倍数数

[编程题]无倍数数

热度指数：2020 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小M得到了n个互不相同的正整数ai，在这n个数中，某个数称为无倍数数当且仅当其他的数都不是它的倍数。请你帮小M找出这n个数中所有的无倍数数，并以升序输出。

输入描述:

第一行包含一个整数n。1≤n≤10⁵

第二行包含n个互不相同的正整数Ai。1≤Ai≤10⁷

输出描述:

按升序输出所有的无倍数数，以空格分隔。

示例1

输入

3
8 4 12

输出

8 12

算法知识视频讲解

路人寅

# -*- coding: utf-8 -*-
def find(a):
    flag = False
    idx = A.index(a)
    for i in range(idx + 1, len(A)):
        if A[i] % a == 0:
            flag = True
            break
    return flag

if __name__ == '__main__':
    n = raw_input()
    A = sorted(map(int, raw_input().split(' ')))
    B = filter(lambda a: not find(a), A)
    print ' '.join(str(b) for b in B) + ' '

就很奇怪的一个题目。。怎么都通过不了。

发表于 2019-04-08 14:44:10 回复(0)

Java

Sen🍓🍀

import java.util.*;

// Set记录, 枚举每个数的因数, 从Set移除
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            set.add(a[i]);
        }

        Arrays.sort(a); // 排序：从小到大
        for (int x : a) {
            for (int i = 2; i * i <= x; i++) { // 2开始, 剔除因数
                if (x % i == 0 && (set.contains(i) || set.contains(x / i) ) ) {
                    set.remove(i);
                    set.remove(x / i);
                }
            }
        }

        set.remove(1); // 1肯定不是, 下面处理结果升序即可
        List<Integer> res = new ArrayList<>(set);
        Collections.sort(res);
        StringBuilder sb = new StringBuilder();
        for (int x : res) sb.append(x).append(' ');
        System.out.println(sb.toString());
    }
}

发表于 2025-10-24 23:11:55 回复(0)

黄宗文

# 简单粗暴，看看集合中其他数是不是它的倍数，如果都不是加入结果集，如果存在剔除它
# 时间复杂度是O(n**2)，暂时没想出效率更高的算法

n = int(input())
ai = list(map(int, input().split()))
res = []
for i in ai:
for j in ai:
if j%i == 0 and j//i != 1:
res.append(i)

print(res)

# 题目有毒吧

发表于 2020-07-23 16:21:11 回复(0)

jsnsacksajsbjd

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,i,j;
    scanf("%d",&n);

    int*a;
    a=(int*)malloc(sizeof(int)*(n+1));
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);//a[i]1~10000000,互不相同
    }

    int p;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                p=a[i];
                a[i]=a[j];
                a[j]=p;

            }
        }

    }
    /*

    for(i=0;i<n;i++)
    {

        printf("%d ",a[i]);
    }
    printf("\n");

*/
    int count=0;
    for( i = 0; i<n; i++)
    {
for(j = i+1; j<n; j++)
        {
            if(a[j]%a[i]==0)
                break;
            else
                continue;

}
        if(j==n)
        {
            if(count==0)
                printf("%d",a[i]);
            else
                printf(" %d",a[i]);
            count++;
        }

    }
    printf("\n");

    return 0;
}

发表于 2019-05-12 11:38:34 回复(0)

冬雪香莹

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long int arr[100001];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    long long int a[100001];
    a[0]=arr[n-1];
    int count=1;
    for(int i=n-2;i>=0;i--)
    {
        int flag=0;
        for(int j=n-1;j>i;j--)
        {
            if(arr[j]%arr[i]==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            a[count]=arr[i];
            count++;
        }
    }
    for(int i=count-1;i>0;i--)
    {
        cout<<a[i]<<" ";
    }
    cout<<a[0]<<endl;
}

自行测试没问题

发表于 2019-04-25 21:28:51 回复(0)

孤傲山鹰

//没过，提示“请检查是否存在数组越界等非法访问情况”，哪位大佬帮忙解决一下

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class wubeishushu {     public static void main(String[] args) {         Scanner input = new Scanner(System.in);         int n = input.nextInt();         int[] arr = new int[n];         for(int i = 0; i < n; i++)             arr[i] = input.nextInt();         Arrays.sort(arr);
        List <Integer> list = new ArrayList<>();
        if(n == 1)
            System.out.println(arr[0]);
        else {
            for(int i = arr.length-2; i >= 0; i--) {
                boolean flag = true;
                for(int j = i+1; j < arr.length; j++) {
                    if(arr[j] % arr[i] == 0) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    list.add(arr[i]);
                }
            }
            if(list.size() > 0) {
                for(int k = list.size()-1; k >= 0; k--)
                    System.out.print(list.get(k) + " ");
            }
            System.out.println(arr[arr.length-1]);
        }         input.close();     }

}

发表于 2019-04-22 18:49:18 回复(0)

𓆡𓆝𓆟𓆜𓆞𓆝𓆟𓆜20190403110475

//怎么都通过不了
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(reader.readLine());
        String[] str = reader.readLine().split(" ");
        ArrayList<Integer> list = new ArrayList<>();
        for (String s : str) {
            list.add(Integer.parseInt(s));
        }
        Collections.sort(list);
        for (int i = list.size() - 1; i >= 0; i--) {
            int max = list.get(i);
            for (int j = 0; j < list.size(); j++) {
                if (i == j) {
                    break;
                }
                if (max % list.get(j) == 0) {
                    list.remove(j);
                    j--;
                    i--;
                }
            }
        }
        for (Integer integer : list) {
            System.out.print(integer+" ");
        }
    }
}

发表于 2019-04-13 21:28:37 回复(0)

迷路了问问道

import java.util.*;
public class Main {         public static void main(String [] args){             Scanner in=new Scanner(System.in);             int n=in.nextInt();             int Ai[]=new int[n];             for(int i=0;i<n;i++){                 Ai[i]=in.nextInt();             }             for(int i=0;i<n-1;i++){                 for(int j=i+1;j<n;j++){                     if(Ai[i]>Ai[j])                     {                         int t=Ai[i];                         Ai[i]=Ai[j];                         Ai[j]=t;                     }                 }             }              for(int i=0;i<n;i++){                  int count=0;                 for(int j=0;j<n;j++){                     if(Ai[j]%Ai[i]!=0)                     {                         count++;                     }                 }                  if(count==n-1)                         System.out.print(Ai[i]+" ");             }         }      }

发表于 2019-04-11 17:47:28 回复(0)

一生白色

n = int(input())
ai = sorted(list(map(int, input().split())))
a = []

for i in range(n-1):
    for j in range(i+1, n):
        if ai[j]%ai[i] == 0:
            a.append(ai[i])
            break
            
out =[i for i in ai if i not in a]
for i in range(len(out)):
    print(out[i],end =' ')

在编译器里跑得好好的，一提交就说语法问题···

发表于 2019-04-09 22:08:32 回复(0)

Disconnect

n = input()
n = int(n)
num = []
ai = sorted(map(int,input().split()))
for i in range(n):
    bo = True
    if ai[i]!=0:
        for j in range(i+1,n):
            if ai[j]%ai[i]==0:
                bo = False
                break
        if bo:
            num.append(ai[i])
print(' '.join(map(str,num))+' ')

很奇怪的一道题，不知道咋回事就是过不了。。。

编辑于 2019-02-10 20:20:12 回复(0)

HPrevInstance

不知道为什么这道题通过不了,不知道是不是有点小问题，说好的输入全部都是正整数确是提醒我出现了除以0的情况，我想知道这道题的例子，我觉得我的代码没问题，扔在下面。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> vec(n);
vector<int> res;
for(int i=0;i<n;i++)
cin>>vec[i];
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++){
int flag=1;
for(int j=i+1;j<n;j++){
if(vec[j]%vec[i]==0){
flag=0;
break;
}
}
if(flag)
res.push_back(vec[i]);
}
sort(res.begin(),res.end());
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
return 0;
}

发表于 2019-01-26 15:24:12 回复(7)