Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Primality Test - Applied Cryptography

Get Embed Code
1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. So that suggests a strategy for finding a large prime--
  2. which is to keep trying guesses until we find one that's prime.
  3. If it's not a prime, then we add 1 and we try again.
  4. Because of what we know about the number of primes being finite
  5. and the density of primes, we know that after a reasonable number of iterations
  6. this will actually find a prime and return that value.
  7. We could do a little better if we assume we start with an odd number
  8. and we'll assert that X is not divisible by 2
  9. since that is very obvious that it would be prime
  10. and increment by 2 here.
  11. What's missing is we need some way to do this "is prime" test.
  12. So here is a naive way to test to the finest prime.
  13. We're going to go through the numbers from 2 to X minus 1,
  14. checking whether X is divisible by each of those.
  15. If it is divisible by any of those,
  16. that would mean that it is a composite number
  17. and we should return False.
  18. If we try them all and it's not divisible by any of those, well then it's prime.
  19. So the question is: Would this work?
  20. The possible answers are: Yes, this would work fine.
  21. No, it's too slow because the running time is exponential in the value of X.
  22. No because it's too slow because the running time is exponential in the size of X.
  23. And no, because there's a silly bug in my Python code.