1

Co-prime numbers are the numbers whose common factor is only 1.

Problem statement: Given an integer array 'A' of positive numbers, I need to return an array of integers 'B', such that B[i]= count of integers j such that 1 <= j <= A[i] and j is co-prime with respect to A[i]. Ex, for A = [5,8,14], B will be [4,4,6]

Explanation: A[0] = 5, numbers less than 5, i.e 1-4 are prime. So B[0] = 4 A[1] = 8, numbers less than 8 are 1-7, out of which [1,3,5,7] are co-primes, hence B[0]=4 A[2] = 14, the co-primes between 1-13 are [1,3,5,9,11,13], therefore B[2] = 6

Constraints: 1 <= A[i] <= 10(power_of)5 1 <= size of A <= 10(power_of)5

I have a solution in place, but for some reason it returns wrong result for larger arrays, and is also NOT time efficient. Please help me with a better solution, or guide me with how I can optimize mine?

Solution:

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])

The time complexity is bad because it will start counting from 1 for every element in the array.

Niyanta
  • 445
  • 1
  • 8
  • 15
  • 1
    You could consider a different way to [calculate the totient](https://en.wikipedia.org/wiki/Euler%27s_totient_function#Computing_Euler's_totient_function). – גלעד ברקן Aug 19 '21 at 15:16
  • 2
    This is called the Totient or the PHI() function. Here is very efficient example of how to do it for a large range of numbers in VB.net: https://stackoverflow.com/a/1134851/109122 – RBarryYoung Aug 19 '21 at 16:05

1 Answers1

1

I wrote this for rosettacode a few years ago:

require "prime"

def totient(n)
    n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) } 
end
steenslag
  • 76,334
  • 16
  • 131
  • 165