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

No vote yet

3 votes

×

Problem Loading...

Note Loading...

Set Loading...

## 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. – Thaddeus Abiy · 4 years, 4 months ago

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 – Kumar Ashutosh · 4 years, 4 months ago

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). – Carl Joshua Quines · 4 years, 4 months ago

Log in to reply

You could extend this to factoring numbers, but I doubt if the problem is NP-easy. – Carl Joshua Quines · 4 years, 4 months ago

Log in to reply

– Carl Joshua Quines · 4 years, 4 months ago

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 – Bob Yang · 4 years, 4 months ago

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? – Sayan Chowdhury · 4 years, 4 months ago

Log in to reply

– Irvi Firqotul Aini · 4 years, 4 months ago

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...... – Alpha Beta · 4 years, 4 months ago

Log in to reply

– Bob Krueger · 4 years, 4 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.Log in to reply

– Kumar Ashutosh · 4 years, 4 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 meLog 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 – Edward Elric · 4 years, 4 months ago

Log in to reply

– Zi Song Yeoh · 4 years, 4 months ago

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) – Ayush Maheshwari · 4 years, 4 months ago

Log in to reply

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 – Marcus Neal · 4 years, 4 months ago

Log in to reply

– Bob Krueger · 4 years, 4 months ago

So 115 is prime? I think not.Log in to reply

– Aasif Khan · 4 years, 4 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.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. – Anh Huy Nguyen · 4 years, 4 months ago

Log in to reply

– Zi Song Yeoh · 4 years, 4 months ago

115 is obviously not a prime. :)Log in to reply

– Ryuzaki Marodz · 4 years, 4 months ago

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