Back to Subject

Unit 3: GCD and Primality testing - Practice Quiz

CSE329 — Prelude To Competitive Coding 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 The Euclidean algorithm is primarily used to compute which of the following?

Basic Euclidean algorithm Easy
A. The greatest common divisor (GCD) of two integers
B. The sum of two integers
C. The prime factorization of a number
D. The least common multiple only

2 In the Euclidean algorithm, is equal to which of the following?

Basic Euclidean algorithm Easy
A. always
B.
C.
D.

3 What is the terminating condition of the Euclidean algorithm using modulo?

Basic Euclidean algorithm Easy
A. When both numbers are equal
B. When the remainder becomes
C. When the remainder becomes
D. When one number becomes negative

4 What is using the Euclidean algorithm?

Basic Euclidean algorithm Easy
A.
B.
C.
D.

5 The Extended Euclidean algorithm finds integers and satisfying which equation?

Extended Euclidean algorithm Easy
A.
B.
C.
D.

6 The Extended Euclidean algorithm is commonly used to compute which of the following?

Extended Euclidean algorithm Easy
A. The nth prime number
B. The number of divisors
C. The factorial of a number
D. The modular multiplicative inverse

7 If , the total number of divisors of is given by which expression?

Total number of divisors of a number Easy
A.
B.
C.
D.

8 How many divisors does the number have?

Total number of divisors of a number Easy
A.
B.
C.
D.

9 What are all the distinct prime factors of ?

Finding all prime factors of a number Easy
A.
B.
C.
D.

10 Which of the following is NOT considered a prime factor of any number?

Finding all prime factors of a number Easy
A.
B.
C.
D.

11 When trial-dividing to factorize , checking divisors only up to works because:

Finding the prime factors by taking the square root Easy
A. Factors always occur below only
B. Any factor larger than pairs with a factor smaller than
C. is always an integer
D. Numbers above are always prime

12 What is the approximate time complexity of factorizing a number using trial division up to ?

Finding the prime factors by taking the square root Easy
A.
B.
C.
D.

13 A K-jagged number is a number whose all prime factors are:

K-jagged numbers Easy
A. Equal to exactly
B. Multiples of
C. Greater than
D. Less than or equal to

14 A Störmer number is a positive integer for which the greatest prime factor of is:

Stormer numbers Easy
A. Exactly
B. At least
C. Always equal to
D. Less than

15 A frugal number is a number that has:

Frugal number Easy
A. Exactly the same digits as its factorization
B. More digits than its prime factorization (with exponents) uses
C. Fewer digits than its factorization uses
D. No prime factors at all

16 A number is called -smooth if:

P-smooth numbers in given ranges Easy
A. It is a prime greater than
B. It has exactly divisors
C. It is divisible by
D. None of its prime factors exceed

17 Which of the following numbers is -smooth?

P-smooth numbers in given ranges Easy
A.
B.
C.
D.

18 Lemoine's Conjecture states that every odd integer greater than can be expressed as:

Lemoine's Conjecture Easy
A. The sum of two primes
B. The sum of a prime and twice a prime ()
C. The sum of three even numbers
D. The product of two primes

19 Two integers are said to be coprime (relatively prime) if their GCD equals:

Problems based on GCD and primality testing Easy
A. The smaller of the two numbers
B.
C.
D.

20 The relationship between GCD and LCM of two numbers and is given by:

Problems based on GCD and primality testing Easy
A.
B.
C.
D. always

21 Using the Euclidean algorithm to compute , how many division (modulo) steps are performed before reaching a remainder of ?

Basic Euclidean algorithm Medium
A. steps
B. steps
C. steps
D. steps

22 For two consecutive Fibonacci numbers and , the Euclidean algorithm is known to require the maximum number of steps relative to input size. What is ?

Basic Euclidean algorithm Medium
A.
B.
C.
D.

23 The extended Euclidean algorithm finds integers such that . For and , which pair is a valid solution?

Extended Euclidean algorithm Medium
A.
B.
C.
D.

24 The extended Euclidean algorithm is commonly used to compute the modular multiplicative inverse of modulo . This inverse exists if and only if:

Extended Euclidean algorithm Medium
A. is prime
B.
C. is even
D.

25 Given the prime factorization , what is the total number of positive divisors of ?

Total number of divisors of a number Medium
A.
B.
C.
D.

26 A number has exactly positive divisors. What must be true about ?

Total number of divisors of a number Medium
A. is a cube of a prime
B. is the square of a prime
C. is prime
D. is a product of two distinct primes

27 What is the complete set of distinct prime factors of ?

Finding all prime factors of a number Medium
A.
B.
C.
D.

28 When factoring by trial division, after dividing out all factors of a prime , why do we move to the next candidate rather than testing again?

Finding all prime factors of a number Medium
A. can only divide once
B. It reduces the space complexity
C. The next number is always prime
D. All copies of have already been removed

29 When finding prime factors of by trial division, it suffices to test divisors only up to because:

Finding the prime factors by taking the square root Medium
A. Factors above are never prime
B. All prime factors are less than
C. If has no factor , the remaining is prime
D. Division above gives fractions

30 Using the square-root method to factor , up to which integer do we test trial divisors, and what is the conclusion?

Finding the prime factors by taking the square root Medium
A. Up to ; is prime
B. Up to ; is prime
C. Up to ; is prime
D. Up to ; is composite

31 A K-jagged number is a positive integer whose smallest prime factor is greater than or equal to . Which of the following is a -jagged number?

K-jagged numbers Medium
A.
B.
C.
D.

32 For , which property must every -jagged number greater than satisfy?

K-jagged numbers Medium
A. It is divisible by
B. It is prime
C. It is odd
D. It is a perfect square

33 A Størmer number is a positive integer for which the greatest prime factor of is at least . Which of the following is a Størmer number?

Stormer numbers Medium
A.
B.
C.
D.

34 To test whether is a Størmer number, which quantity must be computed and compared against ?

Stormer numbers Medium
A. The smallest prime factor of
B. The sum of prime factors of
C. The greatest prime factor of
D. The number of divisors of

35 A frugal (economical) number has fewer digits than the total digits used in its prime factorization (with exponents). Which of the following is a frugal number?

Frugal number Medium
A.
B.
C.
D.

36 When counting digits of a prime factorization for classifying a frugal number, an exponent of is:

Frugal number Medium
A. Replaced by a zero
B. Counted as one digit
C. Counted as two digits
D. Omitted (not written)

37 A number is -smooth if all its prime factors are . How many -smooth numbers exist in the range (counting )?

P-smooth numbers in given ranges Medium
A.
B.
C.
D.

38 Which of the following numbers is -smooth?

P-smooth numbers in given ranges Medium
A.
B.
C.
D.

39 Lemoine's Conjecture states that every odd integer greater than can be expressed as:

Lemoine's Conjecture Medium
A. where are primes
B. where are primes
C. where are primes
D. where are primes

40 Two integers and satisfy and . What is the value of ?

Problems based on GCD and primality testing Medium
A.
B.
C.
D.

41 For the Euclidean algorithm with , it is known that the worst-case number of division steps occurs for consecutive Fibonacci numbers. If requires exactly modulo operations, what is in terms of ?

Basic Euclidean algorithm Hard
A.
B.
C.
D.

42 Using the Extended Euclidean algorithm, find integers satisfying with the coefficients returned by the standard recursive implementation.

Extended Euclidean algorithm Hard
A.
B.
C.
D.

43 Let . How many divisors of are perfect squares?

Total number of divisors of a number Hard
A.
B.
C.
D.

44 Let . How many divisors of are perfect squares?

Total number of divisors of a number Hard
A.
B.
C.
D.

45 When performing trial division to factor , why is it sufficient to check divisors only up to ?

Finding all prime factors of a number Hard
A. Because divisors above are never prime
B. Because all primes are less than
C. If has no factor , the remaining itself must be prime
D. Because is always an integer for composites

46 Consider factoring (a prime) by trial division up to . Approximately how many trial divisions by candidate integers are performed in the naive (all-integers) approach?

Finding the prime factors by taking the square root Hard
A.
B.
C.
D.

47 A positive integer is called -jagged (rough) if all its prime factors are greater than or equal to . Which of the following is a -jagged number?

K-jagged numbers Hard
A.
B.
C.
D.

48 How many -jagged numbers (numbers whose smallest prime factor is , including ) exist in the range ?

K-jagged numbers Hard
A.
B.
C.
D.

49 A Størmer number is a positive integer for which the greatest prime factor of is at least . Which of the following is NOT a Størmer number?

Stormer numbers Hard
A.
B.
C.
D.

50 For , evaluate whether it is a Størmer number by computing the greatest prime factor of and comparing with .

Stormer numbers Hard
A. Yes, greatest prime factor
B. No, greatest prime factor
C. No, greatest prime factor
D. Yes, greatest prime factor

51 A frugal (economical) number has strictly fewer digits in its prime factorization (with exponents written out) than itself. Which of the following is a frugal number?

Frugal number Hard
A.
B.
C.
D.

52 For , determine whether it is frugal by comparing the digit count of against the digit count of its prime factorization (exponents included).

Frugal number Hard
A. Frugal: digits vs digit
B. Not frugal: digits vs digits
C. Not frugal: digits vs digits
D. Frugal: digits vs digits ()

53 How many -smooth numbers (numbers of the form ) exist in the range ?

P-smooth numbers in given ranges Hard
A.
B.
C.
D.

54 Which of the following numbers is -smooth but NOT -smooth?

P-smooth numbers in given ranges Hard
A.
B.
C.
D.

55 Lemoine's Conjecture states that every odd integer greater than can be written as where and are primes. Which decomposition is a valid Lemoine representation of ?

Lemoine's Conjecture Hard
A.
B.
C.
D.

56 For the odd number , how many distinct Lemoine representations (with prime, ordered pairs) exist?

Lemoine's Conjecture Hard
A.
B.
C.
D.

57 Given and , if and and , what is ?

Problems based on GCD and primality testing Hard
A.
B.
C.
D.

58 For the Miller-Rabin primality test on , a witness proves compositeness when and for all , where with odd. For (a Carmichael number), what is the pair ?

Problems based on GCD and primality testing Hard
A.
B.
C.
D.

59 The modular inverse of modulo computed via the Extended Euclidean algorithm is:

Extended Euclidean algorithm Hard
A.
B.
C.
D.

60 If denotes the number of divisors of , and for distinct primes , for which condition is odd?

Total number of divisors of a number Hard
A. and are both odd
B. is even
C. is prime
D. Both and are even (i.e. is a perfect square)
Previous MCQ
Unit 2
Next MCQ
Unit 4