Euclid’s Algorithm MCQ

Test your knowledge with important Euclid’s Algorithm MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Euclid’s Algorithm MCQs at Bissoy

• What is the GCD of 20 and 12 using Euclid’s algorithm?
  ক

  8

  খ

  2

  গ

  4

  ঘ

  6
• What is the total running time of the binary GCD algorithm?
  ক

  O(N)

  খ

  O(N2)

  গ

  O(log N)

  ঘ

  O(N log N)
• What is the formula for Euclidean algorithm?
  ক

  GCD (m,n) = GCD (n, m mod n)

  খ

  LCM(m,n)=LCM(n, m mod n)

  গ

  GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)

  ঘ

  LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)
• Euclidean algorithm does not require the calculation of prime factors.
  ক

  True

  খ

  False
• What is the total running time of Euclid’s algorithm?
  ক

  O(N)

  খ

  O(N log M)

  গ

  O(N log N)

  ঘ

  O(log N +1)
• If GCD of two numbers is 1, then the two numbers are said to be ________
  ক

  Co-prime numbers

  খ

  Prime numbers

  গ

  Composite numbers

  ঘ

  Rational numbers
• Which of the following is the correct mathematical application of Euclid’s algorithm?
  ক

  Determination of prime numbers

  খ

  Lagrange’s four square theorem

  গ

  Cauchy-Euler theorem

  ঘ

  Residue theorem
• According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?
  ক

  Less than five times the number of digits

  খ

  More than five times the number of digits

  গ

  Less than two times the number of digits

  ঘ

  More than two times the number of digits
• The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero.
  ক

  True

  খ

  False
• Which of the following is not an application of Euclid’s algorithm?
  ক

  Simplification of fractions

  খ

  Performing divisions in modular arithmetic

  গ

  Solving quadratic equations

  ঘ

  Solving diophantine equations
• If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?
  ক

  12

  খ

  6

  গ

  4

  ঘ

  2
• Who invented Euclid’s algorithm?
  ক

  Sieve

  খ

  Euclid

  গ

  Euclid-Sieve

  ঘ

  Gabriel lame
• Euclid’s algorithm is used for finding ___________
  ক

  GCD of two numbers

  খ

  GCD of more than three numbers

  গ

  LCM of two numbers

  ঘ

  LCM of more than two numbers