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

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.

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

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.

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?

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

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

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.

@Aasif Khan
–
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');

## Comments

Sort by:

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

Log in to reply

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

Log in to reply

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

Log in to reply

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.

Log in to reply

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

Log in to reply

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

Log in to reply

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?

Log in to reply

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

Log in to reply

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

Log in to reply

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.

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

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)

Log in to reply

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

Log in to reply

So 115 is prime? I think not.

Log in to reply

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.

Log in to reply

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');

readln

end.

Log in to reply

115 is obviously not a prime. :)

Log in to reply

Log in to reply