Prime Number Testing

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...

#Math

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 prime since $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! :)

Zi Song Yeoh - 8 years, 4 months ago

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???

A Brilliant Member - 8 years, 4 months ago

just divisibility rules can help you there

Harshit Kapur - 8 years, 4 months ago

shouldn't that be largest prime number?

Tan Li Xuan - 8 years, 4 months ago

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

Tan Li Xuan - 8 years, 4 months ago

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.

Harshit Kapur - 8 years, 4 months ago

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

A Brilliant Member - 8 years, 4 months ago

Unfortunately this test is not deterministic...

Lawrence Sun - 8 years, 4 months ago

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.

Harshit Kapur - 8 years, 4 months ago

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...

A Brilliant Member - 8 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$