Alice is trying to find a prime with 50 digits. She has an algorithm (and we wil

Question

Alice is trying to find a prime with 50 digits. She has an algorithm (and we will see these
soon) to test a given number for primality, but she has a very slow machine and this is relatively
time consuming. She proposes to just write down a 50 digit number n, then look at n, n + 1,
n + 2, . . . until the test gives a prime. To save some time she will do a preliminary sieve
by discarding all even numbers and dividing by 3 and 5. Use the Prime Number Theorem to
determine the expected number of times she should run the test before having a good chance
of finding a prime.
[

Explanation / Answer

32

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.