Alice is trying to find a prime with 50 digits. She has an algorithm (and we wil
ID: 1890858 • Letter: A
Question
Alice is trying to find a prime with 50 digits. She has an algorithm (and we will see thesesoon) 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
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.
Let's begin by defining the Prime Number Theorem. It basically states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N).
We want to determine the expected number of times she should run the test before having a good chance of finding a prime.
Well, that would be:
n=1N 1/ln(n), aka the summation of 1/ln(n) from n = 1 to n = N
Next, we subtract all even numbers (n+1)'s and all 5's or 10's:
n=1N 1/ln(n) - 1/ln(n+1) - 1/ln(5n)
I hope that you found this answer useful towards your studies. It took a considerable amount of thought, time, and effort to compose, and and I'd sincerely appreciate a lifesaver rating! It would really make my day, and will allow me to continue answering your questions :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.