I was recently playing around in Python, and I wrote a program to check if a given number is prime. It works by checking to see if its divisible by each number other than 1 leading up to itself. It works well for small numbers but for very large numbers it takes a very very long time. I was wondering if there are programs that can see if a number is prime in a different and more efficient way.

  • 4
    $\begingroup$ Did you have a look on Wikipedia yet? en.wikipedia.org/wiki/Primality_test $\endgroup$
    – Juho
    Feb 12, 2023 at 8:40
  • 1
    $\begingroup$ What do you call "very large numbers" exactly ? $\endgroup$
    – user16034
    Feb 12, 2023 at 9:37
  • $\begingroup$ Did you at least stop the search at the square root of the input number ? Though the method of successive divisions is quite poor, this criterion improves it significantly. $\endgroup$
    – user16034
    Feb 12, 2023 at 9:40


Browse other questions tagged or ask your own question.