Waste less time on Facebook — follow Brilliant.
×

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
4 years, 4 months ago

No vote yet
3 votes

Comments

Sort by:

Top Newest

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

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

Log in to reply

@Carl Joshua Quines I doubt you'd come across a problem that requires that though. Carl Joshua Quines · 4 years, 4 months ago

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

@Sayan Chowdhury then what is the manual solution since there's so many number, can you explained it? Irvi Firqotul Aini · 4 years, 4 months ago

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

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

Log in to reply

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

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

Log in to reply

@Edward Elric Correction : Primes are in the form of 4k + 1 or 4k + 3(i.e. odd) except for 2. Zi Song Yeoh · 4 years, 4 months ago

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

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

Log in to reply

@Ayush Maheshwari So 115 is prime? I think not. Bob Krueger · 4 years, 4 months ago

Log in to reply

@Bob Krueger 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 · 4 years, 4 months ago

Log in to reply

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

readln

end. Anh Huy Nguyen · 4 years, 4 months ago

Log in to reply

@Bob Krueger 115 is obviously not a prime. :) Zi Song Yeoh · 4 years, 4 months ago

Log in to reply

@Zi Song Yeoh hei Zi Song could you add me on facebook.. my fb is ryuzaki marodz thx! im malaysian too~ Ryuzaki Marodz · 4 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...