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 greater than with exactly two positive divisors
C. A number divisible by every positive integer smaller than itself
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. , followed by checking every remaining integer
B.
C.
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. Finding only the largest divisor of a number
B. Converting a decimal number into binary notation
C. Writing a number as a sum of consecutive integers
D. Writing a number as a product of smaller integers

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. An additional composite factor that must always be ignored
B. An additional prime factor
C. The number of prime factors
D. The square root of the original number

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 convert every exponent into a prime number before multiplication
C. To list every prime efficiently
D. To compute powers 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 complete prime factorization
B. A probable-prime result
C. A guaranteed proof for every number after testing only one randomly selected base
D. A sorted list of divisors

13 What does the Sieve of Eratosthenes find?

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

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

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

15 What is the segmented sieve mainly used for?

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

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. Bubble sort
B. Linear search
C. A segmented sieve that stores every integer from to the largest possible exponent
D. Binary exponentiation

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 prime number
B. is neither prime nor composite
C. is a composite number
D. is both prime and 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. Only the divisors and
B.
C.
D. Every number from to

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. Every number has a divisor below
C. Numbers above are always prime
D. A factor pair cannot both exceed

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. An invalid intermediate value
B. A repeated factor of the original divisor
C. A guaranteed composite factor
D. A remaining prime 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 prevents the same prime factor from being counted repeatedly
C. It guarantees that all divisors are prime
D. It reduces the number before testing later factors

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 exponent is increased by one
B. The result is divided by the current base
C. The result is multiplied by the current base
D. The base is replaced by its square only

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. Some composites satisfy the tested congruence for selected bases
B. Prime numbers never satisfy modular congruences
C. The exponent is always larger than the input number
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. The sieve stores only perfect squares
B. Every multiple below is equal to
C. All smaller multiples were already marked by smaller factors
D. Multiples below are always prime

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. Primes up to
C. Primes up to
D. Only primes between and

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. Run a sieve up to
B. Test divisors only up to
C. Test prime divisors only up to
D. Check whether is an even number

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 no smaller divisor
B. is composite because it is not prime
C. is neither prime nor composite
D. is prime because it has one positive 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 divisor larger than divides another divisor
B. At least one of and is at most
C. Both and are always below
D. Every composite number has a prime factor equal to

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 always performs exactly iterations
B. The loop incorrectly classifies every perfect square
C. The loop skips all even candidate divisors
D. The product can overflow before comparison

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. Append twice because the original number may contain
C. Restart trial division because may still be composite
D. Discard because the loop has already passed its square root

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. Some Carmichael numbers pass for every coprime base
B. Every odd composite passes for every nonzero base
C. Binary exponentiation changes the tested congruence
D. Fermat's theorem applies only to primes below

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

Sieve of Eratosthenes Hard
A. The values below cannot be divisible by
B. Every smaller multiple of is itself a prime number
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 palindromes ending in an even digit need testing
B. Only odd-length palindromes need to be tested
C. Only palindromes whose digit sum is divisible by need testing
D. Only even-length palindromes need to be tested
Previous MCQ
Unit 1
Next MCQ
Unit 3