Probability in Computer Science · Randomized Algorithms

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Below, we design an efficient randomized algorithm for the string equality problem. This protocol needs to select a random prime number.

Problem. Test your intuition!

Take a random integer from \([n]\). What is the probability that it is prime?

5 points

  1. a constant

  2. about \(\frac{1}{\ln n}\)

  3. about \(\frac{1}{\sqrt{n}}\)

  4. about \(\frac{1}{n}\)