最大互质子集 [英] Maximum coprime subset

问题描述

鉴于阵列A1，A2。 。 。 AN是什么阵列这样的最大子集的每对元件中的子集是互质的大小。

Given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.

实施例：设N = 5和阵列是[2 3 2 3 2]，然后回答是2

Example : Let N=5 and array be [2 3 2 3 2] then answer is 2

说明：最大的子集将采取之一的[0]，A [1]，A [2]，并采取之一的[3]，A [4]

Explanation : The largest subset would be taking one of A[0], A[1], A[2] and taking one of A[3], A[4].

N可以在最高50如何处理这个问题？

N can be at max 50. How to approach this question ?

推荐答案

由于所有的我你知道， 1≤艾≤50 ，你可以先过滤输入，之后暴力破解变得可行。

Since for all i you know that 1 ≤ Ai ≤ 50, you can first filter the input, after which bruteforcing becomes feasible.

您可以随时选择所有素数的子集，因为每个黄金至少是一样好素（任意倍数对于给定的素数 P ，如果一个整数 X 是互质与一些 K * X ，那么它也互质与 P ）。之后，你可以删除选定的素数的倍数，因为他们不能在结果中。

You can always select all primes for your subset, because each prime is at least as good as any multiple of that prime (for a given prime p, if an integer x is coprime with some k * x, then it is also coprime with p). After that you can remove all multiples of the selected primes, because they cannot be in the result.

有关更多的滤波，考虑以下几点：每个整数都可以被唯一写成素数的乘积，例如：

For even more filtering, consider the following: every integer can be uniquely written as a product of primes, for instance:

 2 = 21
 6 = 2131
40 = 2351

对于整数 X ，让我们写 X <子> 0 与相应的整所有的质因子具有功率1。例如，如果 X = 40（2 3 5 1 ），然后 X <子> 0 = 10（2 1 5 1 ）。我们不需要考虑质数与功耗＆GT; 1 ，因为对于每一个整数是认为，如果 X 和是是互质的，那么是 X <子> 0 和是。既然你只关心子集的大小，可以相互替换 X 按 X <子> 0 。

For an integer x, let's write x0 for the corresponding integer with all prime factors having power 1. For example, if x = 40 (2351), then x0 = 10 (2151). We do not need to consider primes with power >1, because for every integer y holds that if x and y are coprime, then so are x0 and y. Since you are only interested in the size of the subset, you can replace each x by x0.

有低于50，只有14号是没有素数，有电无素因子＆GT; 1

There are only 14 numbers below 50 that are no prime and have no prime factor with power >1.

6, 10, 14, 15, 21, 22, 26, 30, 33, 34, 35, 38, 39, 42

数量减少 X <子> 0 此组的成员。既然有这么几个，你可以简单地暴力破解，以便找到最大的子集。

The reduced numbers x0 are members of this set. Since there are so few, you can simply bruteforce in order to find the biggest subset.

这篇关于最大互质子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！