Friends, what do you suggest will be quickest way to test whether a number is prime or not?? Testing for forms 4k+-1 or 6k+-1 is useful to test if it is not prime,but doesn't ensure sure results for a number being prime...

There is a faster method.
Its called miller rabin primality test, and is much much faster than trial division.
But it can't be used if you're looking to check primes manually.

With computers, miller rabin primality test is very fast
You can read more about it here

Its main advantage is that you don't have to go about calculating primes uptill \(\sqrt{n}\), and then checking each.

Well,if you go for programming then finding primes,& then storing them in an array is a better way indeed...& many programming techniques are available,& the computer has to work....I'm looking for the mathematical interpretation,if any...

Thanks for your suggestion,I knew that the largest number which can divide a composite is it's square root...however I'm looking for quick eye techniques,does anyone know one???

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestThere is a faster method. Its called miller rabin primality test, and is much much faster than trial division. But it can't be used if you're looking to check primes manually.

With computers, miller rabin primality test is very fast You can read more about it here

Its main advantage is that you don't have to go about calculating primes uptill \(\sqrt{n}\), and then checking each.

Log in to reply

For programming however,the miller rabin primality test is indeed a cool algorithm...

Log in to reply

Well,if you go for programming then finding primes,& then storing them in an array is a better way indeed...& many programming techniques are available,& the computer has to work....I'm looking for the mathematical interpretation,if any...

Log in to reply

Unfortunately this test is not deterministic...

Log in to reply

But it can be made deterministic. Read here

And it doesn't take too much to do so. Here is an implementation in python.I haven't added support for too big numbers, but it can be done easily.

Log in to reply

To test whether if a number is a prime, we just need to test whether if the number, \(n\), is divisible by any

prime\(\leq \sqrt{n}\).Example : \(103\) is a

primesince \(2, 3, 5, 7 \nmid 103\). On the other hand, \(91\) is since \(7 \mid 91\).This works since if a number is composite, it must have a prime factor \(\leq \sqrt{n}\).

Hope this helps! :)

Log in to reply

Wouldn't a prime number sieve be faster for the smaller primes?

Log in to reply

Thanks for your suggestion,I knew that the largest number which can divide a composite is it's square root...however I'm looking for quick eye techniques,does anyone know one???

Log in to reply

just divisibility rules can help you there

Log in to reply

shouldn't that be largest prime number?

Log in to reply