# How to find whether a number is prime or not

Is there an algorithm to find whether a number (especially big ones like 10001 etc...) is a prime or not. As it is very hard to test its divisibility by smaller primes. Kindly suggest me a way if anyone knows..... Please reply......

Note by Kumar Ashutosh
5 years, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 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"
MathAppears 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}$$

Sort by:

You can check if any of the numbers below the square root of the number divide the number. If you are talking about computer algorithms,a neat way is the miller rabin probabilistic primality test it is easy to implement. If you are looking for practical and faster methods you could use a segemented sieve of erastothenes to generate a set primes between a given interval of numbers and check if your prime is within that set.

- 5 years, 10 months ago

There is a method but sometimes very long..Let that number be x.Find a number which is greater than x and also the nearest square to x.Like if we had to check for 151, then its nearest square and greater that it is 169.Its square root is 13.So by this method you got a limit or a boundary under which we have to check.Like square root of 169 is 13, so we have to divide 151 by primes smaller that or equal to 13.i.e 2,3,5,7,11,and 13.If none of them is divide x, then x is a prime number.I also want to know a method by which we can check for larger ones......

- 5 years, 10 months ago

There's no need to test 13 in your example. You need only test the primes that are strictly smaller than the square root of the number.

- 5 years, 10 months ago

ya! this is a better way. Its okay for numbers up to 1000 or so. As you also mentioned I doesn't work for big numbers.... but thanks for helping me

- 5 years, 9 months ago

hello,///// by the way i am giving you this url to find out a number to be prime or not.........check it out.....a number of even 50 digits long can be showed prime or not by this website...........right dude?? ........... 41328906778270922480177076383264980593161395777111 is a prime number..........did u know that?????........then check it ..............the URL is.......................................................... http://www.wolframalpha.com/input/?i=41328906778270922480177076383264980593161395777111+is+a+prime+number?

- 5 years, 10 months ago

then what is the manual solution since there's so many number, can you explained it?

- 5 years, 9 months ago

mostly, the numbers that are 1 or 5 mod 6 are prime

- 5 years, 9 months ago

There's an implementation of the sieve of Eratosthenes, you could probably optimize that (if you're talking about computer algorithms).

- 5 years, 9 months ago

You could try some multiple tests, one could be it must be in the form 6n+1 or 6n-1, if it passed that (a small fraction of numbers pass that), then you could try dividing with the smaller prime numbers (almost all composite large numbers have about a prime number less than its fourth root as a factor), before trying to brute force with the sieve. If you use the sieve, you could try only the primes strictly less than the number's square root. You could generalize even further by noting that all primes are in the form 30n+{1, 7, 11, 13, 17, 19, 23, 29}, and so on.

You could extend this to factoring numbers, but I doubt if the problem is NP-easy.

- 5 years, 9 months ago

I doubt you'd come across a problem that requires that though.

- 5 years, 9 months ago

hello everyone! I am not looking for a computer program or a website for this. I want to know a method which i can apply in exams.... thanks for your comments........... keep commenting

- 5 years, 9 months ago

Primes are simply of the form 4n+1 or 4n+3 and sometimes a mersenne's number of the form 2^n-1

- 5 years, 9 months ago

Correction : Primes are in the form of 4k + 1 or 4k + 3(i.e. odd) except for 2.

- 5 years, 9 months ago

There a nice trick:

case 1:
let the number be "x" find x-1 if it is divisible by six it is prime if not then go to case 2

CASE2 subtract 5 from the number if it is divisible by six it is prime.

eg; 13 - 1 = 12 (prime) 17- 5 = 12 (prime)

- 5 years, 10 months ago

This is not true. If x = 25, then x-1 is divisible by 6; yet 25 is not prime.

You are probably thinking of the fact that if a number p>3 is prime, then p = 6k+1 or p = 6k-1 for some integer k. That statement is true. However, its converse is not true.

You can read more about primality testing here: http://en.wikipedia.org/wiki/Primality_test

- 5 years, 10 months ago

So 115 is prime? I think not.

- 5 years, 10 months ago

Yup there's a sophisticated algorithm called as the AKS primality test that was developed back in the 2000s; three people from Indian Institute of Technology, Kanpur developed the first ever polynomial time primality test algorithm.

- 5 years, 10 months ago

As Assif K. says, there is. However I doubt if any math challenges involve large prime numbers, unless in the year 2011. If you want to check whether a number is a prime, visit wolframalpha.com, or if Internet is not accessible, create your own program to do your work! You can consider Pascal, C, C++, ... The idea is to let a variable i run from 2 to (n-1), and if n is divisible by i, plus 1 to a variable s (usually I set s=0 first).

After that check if s=0 then n is a prime, otherwise it is not.

Here is a sample program for Borland Pascal:

var s,i:integer; n:longint;

begin

s:=0; writeln('Enter number n:'); readln(n);

for i:=2 to (n-1) do if n mod i=0 then s:=s+1;

if s=0 then writeln('n is a prime number') else writeln('n is not a prime number');

end.

- 5 years, 9 months ago

115 is obviously not a prime. :)

- 5 years, 9 months ago

hei Zi Song could you add me on facebook.. my fb is ryuzaki marodz thx! im malaysian too~

- 5 years, 9 months ago

×