Return 包含互质数的数组

Question

互质数是公因数仅为1的数。

问题陈述： 给定一个正数整数数组 'A'，我需要 return 一个整数数组 'B'，使得 B[i]= 整数 j 的计数，使得 1 <= j <= A[i] 和 j 关于 A[i] 互质。例如，对于 A = [5,8,14]，B 将为 [4,4,6]

解释： A[0] = 5，小于5的数，即1-4为质数。所以 B[0] = 4 A[1] = 8，小于8的数为1-7，其中[1,3,5,7]为互质数，故B[0]=4 A[2] = 14，1-13之间的互质数为[1,3,5,9,11,13]，因此B[2] = 6

约束： 1 <= A[i] <= 10(power_of)5 1 <= A 的大小 <= 10(power_of)5

我有一个解决方案，但由于某些原因，它 return 对于较大的数组来说是错误的结果，而且也不省时。请帮助我提供更好的解决方案，或指导我如何优化我的解决方案？

解法：

class CoPrime
  def count_coprime(input)
    array = []
    input.each do |i|
        array << (1...i).count { |a| i.gcd(a) == 1 } #gcd function from integer class
    end
    print "The count of co prime for #{input} are #{array}\n"
  end
end

c = CoPrime.new
c.cout_coprime([5,8,14])

时间复杂度很差，因为它将对数组中的每个元素从 1 开始计数。

Answer 1

我几年前为 rosettacode 写的：

require "prime"

def totient(n)
    n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) } 
end

Return 包含互质数的数组

Return array containing count of co-primes

ruby

algorithm

sliding-window