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
8 years, 2 months ago
No vote yet
3 votes
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:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
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.
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.
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
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?
mostly, the numbers that are 1 or 5 mod 6 are prime
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.
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
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.
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
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
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.
115 is obviously not a prime. :)
Log in to reply
hei Zi Song could you add me on facebook.. my fb is ryuzaki marodz thx! im malaysian too~