Back to Subject

Unit 2: Primality Testing - Practice Quiz

CSE330 — Competitive Coding Approaches-Techniques 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is a prime number?

Introduction to Primality Testing Easy
A. A positive integer that is always odd
B. A number divisible by every positive integer smaller than itself
C. A number greater than with exactly two positive divisors
D. A number greater than with exactly three positive divisors

2 Which of the following numbers is prime?

Introduction to Primality Testing Easy
A.
B.
C.
D.

3 In the primality test, up to which value are possible divisors checked?

O(sqrt(n)) Algorithm for Primality Testing Easy
A.
B.
C.
D.

4 Which condition can be used to test divisors without directly calculating ?

O(sqrt(n)) Algorithm for Primality Testing Easy
A.
B.
C. , followed by checking every remaining integer
D.

5 What is the prime factorization of ?

Factorization of a number Easy
A.
B.
C.
D.

6 Which statement correctly describes factorization?

Factorization of a number Easy
A. Writing a number as a product of smaller integers
B. Writing a number as a sum of consecutive integers
C. Converting a decimal number into binary notation
D. Finding only the largest divisor of a number

7 After dividing out all prime factors up to , what does a remaining value greater than represent?

Finding prime factors by taking the square root Easy
A. The square root of the original number
B. An additional prime factor
C. An additional composite factor that must always be ignored
D. The number of prime factors

8 Which prime factor should be tested first when factorizing by trial division?

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

9 What is the main purpose of binary exponentiation?

Binary Exponentiation Easy
A. To factor every number efficiently
B. To compute powers efficiently
C. To convert every exponent into a prime number before multiplication
D. To list every prime efficiently

10 Which identity is used when the exponent is even in binary exponentiation?

Binary Exponentiation Easy
A.
B.
C.
D.

11 According to Fermat's little theorem, if is prime and is not divisible by , which congruence holds?

Fermat method Easy
A.
B.
C.
D.

12 What kind of result does the Fermat primality method generally provide?

Fermat method Easy
A. A sorted list of divisors
B. A complete prime factorization
C. A guaranteed proof for every number after testing only one randomly selected base
D. A probable-prime result

13 What does the Sieve of Eratosthenes find?

Sieve of Eratosthenes Easy
A. All factors of one given number
B. Only prime palindromes up to a limit
C. Only the largest prime below a limit
D. All primes up to a given limit

14 When processing a prime in the standard sieve, from which value can its composite multiples be marked?

Sieve of Eratosthenes Easy
A.
B. , because every smaller multiple must be prime
C.
D.

15 What is the segmented sieve mainly used for?

Segmented Sieve Easy
A. Checking whether every number in memory has exactly two prime factors
B. Finding primes within an interval
C. Computing one power with repeated squaring
D. Finding the binary form of every number

16 Which primes are needed to mark composites in a segment ending at ?

Segmented Sieve Easy
A. Primes from to
B. Only primes greater than
C. Every prime up to
D. Primes up to

17 Which technique is most useful when the values in Mansi's series involve repeatedly computing large powers?

Mansi and her series Easy
A. A segmented sieve that stores every integer from to the largest possible exponent
B. Binary exponentiation
C. Bubble sort
D. Linear search

18 If a term of Mansi's series is defined as , what is its value for ?

Mansi and her series Easy
A.
B.
C.
D.

19 If pens are divided into equal collections of pens each, how many collections are formed?

Collections of Pens Easy
A.
B.
C.
D.

20 What is the smallest prime palindrome greater than ?

Next prime palindrome Easy
A.
B.
C.
D.

21 Which statement correctly classifies the number ?

Introduction to Primality Testing Medium
A. is a composite number
B. is both prime and composite
C. is a prime number
D. is neither prime nor composite

22 To test whether is prime using the method, which divisors are sufficient to check?

O(sqrt(n)) Algorithm for Primality Testing Medium
A.
B.
C. Every number from to
D. Only the divisors and

23 Why can a primality test stop after checking divisors up to ?

O(sqrt(n)) Algorithm for Primality Testing Medium
A. The square root contains all prime numbers
B. A factor pair cannot both exceed
C. Numbers above are always prime
D. Every number has a divisor below

24 What is the prime factorization of ?

Factorization of a number Medium
A.
B.
C.
D.

25 During trial-division factorization, after all possible factors up to have been removed, what does a remaining value greater than represent?

Factorization of a number Medium
A. A remaining prime factor
B. An invalid intermediate value
C. A repeated factor of the original divisor
D. A guaranteed composite factor

26 Using trial division up to the square root, what are the prime factors of ?

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

27 What is the main advantage of dividing out a factor repeatedly during prime factorization?

Finding prime factors by taking the square root Medium
A. It eliminates the need to test the square root
B. It reduces the number before testing later factors
C. It prevents the same prime factor from being counted repeatedly
D. It guarantees that all divisors are prime

28 Using modular arithmetic, what is the value of ?

Binary Exponentiation Medium
A.
B.
C.
D.

29 What is the time complexity of computing using binary exponentiation?

Binary Exponentiation Medium
A.
B.
C.
D.

30 In binary exponentiation, what operation is performed when the current exponent bit is ?

Binary Exponentiation Medium
A. The base is replaced by its square only
B. The exponent is increased by one
C. The result is divided by the current base
D. The result is multiplied by the current base

31 For a prime number and an integer such that , which congruence is guaranteed by Fermat's Little Theorem?

Fermat method Medium
A.
B.
C.
D.

32 Why can a Fermat primality test incorrectly classify some composite numbers as prime?

Fermat method Medium
A. The exponent is always larger than the input number
B. Prime numbers never satisfy modular congruences
C. Some composites satisfy the tested congruence for selected bases
D. Modular multiplication cannot handle composite values

33 How many prime numbers are there from through ?

Sieve of Eratosthenes Medium
A.
B.
C.
D.

34 When processing a prime in the Sieve of Eratosthenes, why can marking begin at ?

Sieve of Eratosthenes Medium
A. All smaller multiples were already marked by smaller factors
B. Multiples below are always prime
C. Every multiple below is equal to
D. The sieve stores only perfect squares

35 What is the usual time complexity of the Sieve of Eratosthenes for finding all primes up to ?

Sieve of Eratosthenes Medium
A.
B.
C.
D.

36 Which set of primes is required before applying a segmented sieve to the interval ?

Segmented Sieve Medium
A. Primes up to
B. Only primes between and
C. Primes up to
D. Primes up to

37 Which numbers are prime in the interval ?

Segmented Sieve Medium
A.
B.
C.
D.

38 When marking multiples of a base prime in a segment , which starting value is generally correct?

Segmented Sieve Medium
A.
B.
C.
D.

39 Suppose Mansi's series is defined by listing consecutive prime numbers: . What is the th term?

Mansi and her series Medium
A.
B.
C.
D.

40 If a term in Mansi's prime-based series must be checked for primality and its value is , which approach is sufficient for a single check?

Mansi and her series Medium
A. Test prime divisors only up to
B. Check whether is an even number
C. Run a sieve up to
D. Test divisors only up to

41 A deterministic primality tester first handles , then tests divisibility only by primes not exceeding . For , which outcome is mathematically correct?

Introduction to Primality Testing Hard
A. is prime because it has one positive divisor
B. is composite because it is not prime
C. is neither prime nor composite
D. is prime because it has no smaller divisor

42 Suppose is composite with integers . Which fact guarantees that trial division need not test candidate divisors larger than ?

Introduction to Primality Testing Hard
A. Every composite number has a prime factor equal to
B. Every divisor larger than divides another divisor
C. Both and are always below
D. At least one of and is at most

43 Consider for (long long i = 2; i * i <= n; ++i) with signed 64-bit integers. For very large positive , what is the most serious correctness risk?

O(sqrt(n)) Algorithm for Primality Testing Hard
A. The loop incorrectly classifies every perfect square
B. The product can overflow before comparison
C. The loop always performs exactly iterations
D. The loop skips all even candidate divisors

44 After separately rejecting multiples of and , an implementation tests divisors up to . Which update pattern generates exactly these candidates?

O(sqrt(n)) Algorithm for Primality Testing Hard
A. Test and , then set
B. Test and , then set
C. Test and , then set
D. Test and , then set

45 How many positive divisors does have?

Factorization of a number Hard
A.
B.
C.
D.

46 Let , where and are distinct primes. What is the sum of all positive divisors of ?

Factorization of a number Hard
A.
B.
C.
D.

47 A factorization loop repeatedly divides by each candidate while . After the loop, the remaining value is . What must the algorithm do?

Finding prime factors by taking the square root Hard
A. Append once because the remainder is a prime factor
B. Discard because the loop has already passed its square root
C. Append twice because the original number may contain
D. Restart trial division because may still be composite

48 Factor by repeated trial division. Which prime factorization is correct?

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

49 Using modular binary exponentiation, what is ?

Binary Exponentiation Hard
A.
B.
C.
D.

50 An implementation computes during binary exponentiation, where . Which condition is sufficient for ordinary signed 64-bit multiplication to avoid overflow for every step?

Binary Exponentiation Hard
A.
B.
C.
D.

51 A Fermat primality test checks whether . Which composite number passes this test for base ?

Fermat method Hard
A.
B.
C.
D.

52 Why can repeating Fermat tests with many bases still fail to prove that an odd integer is prime?

Fermat method Hard
A. Fermat's theorem applies only to primes below
B. Binary exponentiation changes the tested congruence
C. Every odd composite passes for every nonzero base
D. Some Carmichael numbers pass for every coprime base

53 In a sieve up to , why may marking multiples of a prime begin at ?

Sieve of Eratosthenes Hard
A. Every smaller multiple of is itself a prime number
B. The values below cannot be divisible by
C. Starting at would omit multiples above
D. Every smaller multiple of has a prime factor below

54 A sieve stores only odd numbers from through and handles separately. For an odd prime , which marking sequence is correct?

Sieve of Eratosthenes Hard
A.
B.
C.
D.

55 To mark multiples of a prime in an inclusive segment , which starting value avoids marking itself as composite while also skipping products already handled conceptually below ?

Segmented Sieve Hard
A.
B.
C.
D.

56 A segmented sieve processes . Up to what limit must base primes be precomputed to mark every composite in the segment?

Segmented Sieve Hard
A.
B.
C.
D.

57 Define Mansi's series by . For every , what is ?

Mansi and her series Hard
A.
B.
C.
D.

58 Define Mansi's series by and equal to the smallest prime strictly greater than . What is ?

Mansi and her series Hard
A.
B.
C.
D.

59 A collection has pens and must be divided into equal nonempty groups, with neither one group nor groups of one pen allowed. For which is such a division impossible?

Collections of Pens Hard
A.
B.
C.
D.

60 For an integer , which observation most effectively reduces the search for the smallest prime palindrome greater than ?

Next prime palindrome Hard
A. Only odd-length palindromes need to be tested
B. Only palindromes whose digit sum is divisible by need testing
C. Only even-length palindromes need to be tested
D. Only palindromes ending in an even digit need testing
Previous MCQ
Unit 1
Next MCQ
Unit 3