Page 1 of 1
5. Given a large integer N, you generate prime numbers in the follow- ing way: pick a random n < N, run a primality test
Posted: Mon May 09, 2022 10:39 am
by answerhappygod
- 5 Given A Large Integer N You Generate Prime Numbers In The Follow Ing Way Pick A Random N N Run A Primality Test 1 (76.47 KiB) Viewed 29 times
5. Given a large integer N, you generate prime numbers in the follow- ing way: pick a random n < N, run a primality test on it, and try again. Suppose your primality test is completely accurate; what's the probability that you find at least one prime in 4 tries? (You're allowed to assume the Prime Number Theorem, which basically says there are about N/log(N) primes less than N)