作为两个正整数之间的单个运算,我们理解将其中一个数乘以某个素数或将其除以(假设它可以除以该素数而没有余数).表示为d(a,b)的a和b之间的距离是将数字a变换为数字b所需的最小操作量.例如,d(69,42)= 3.
请记住,我们的函数d确实具有距离的特征 - 对于任何正的整数a,b和c,我们得到:
a)d(a,a)== 0
b)d(a,b)== d(b,a)
c)满足三角形d(a,b)+ d(b,c)> = d(a,c)的不等式.
您将获得一系列正整数a_1,a_2,...,a_n.对于它们的每个a_i输出这样的a_j(j!= i),d(a_i,a_j)尽可能低.例如,长度为6:{1,2,3,4,5,6}的序列应输出{2,1,1,2,1,2}.
这对我来说真的很难.我认为有用的是:
a)如果a_i是素数,我们不能做任何小于a_i的东西(除非它是1)所以唯一的操作是乘法.因此,如果我们在集合中有1,则对于每个素数d(this_number,1)是最低的.
b)同样,1 d(1,any_prime_number)是最低的.
c)对于非素数,我们检查我们在其因子的集合或乘积中是否有任何因子
不过,这就是我所能推断的.最糟糕的是,我知道这种算法运行并检查所有可能性需要永恒...你能不能试着帮我吧？该怎么做？