+8 Hello!
I have been wondering about this for a long time: Is there a quick way to find out if a number is prime? For example, a number like 727813 would require large amounts of time to figure out if its prime (using the normal way of dividing smaller numbers into this large number). If there is a way, can it be done without using a calculator?
+170 No, there isn't a magic bullet method for determining whether or not a number is prime, but if you are dividing the number you only have to test up to its square root. See https://en.wikipedia.org/wiki/Primality_test
+177 Unfortunately, I am not aware of a more efficient full-proof primality test that does not involve testing all the prime factors not exceeding the square root of the number to test. However, there exists probabilistic primality tests that are computationally much faster to perform. This essentially means that the outcome of these tests have a high probability of giving the correct answer, but they can be wrong. I have not read too much about these probabilistic primality tests, but a lot of them are likely above my mathematical chops.
If you are interested in generating many prime numbers at once, then you can explore the Sieve of Erathosenes. I have used this before on a previous college computer science project, and I think the algorithm is understandable to most laypeople.
