Trial division: To test if n is prime, one can check for every k≤ sqrt (n) if k divides n. If no divisor is found, then n is prime.
Or 6k+/-1
I agree with the comments of the previous colleagues, but could not avoid mentioning the coincidence that the first author of the first proven deterministic primality test in polynomial time* - the AKS primality test - seems to have your name, except for one letter: "Agrawal", from the famous 2002 Agrawal–Kayal–Saxena primality test.
Synchronicity?
*not neccessarily useful in practice
Kind regards.
Fernando.
The big question is whether you want probabilistic tests or deterministic tests.
The wikipedia page here https://en.wikipedia.org/wiki/Primality_test is very good, and should answer your questions.
Dear Pankaj,
The attached paper lists four different (both deterministic and probabilistic) and useful primality tests...
Best of luck,
I agree with the comments of the previous colleagues, but could not avoid mentioning the coincidence that the first author of the first proven deterministic primality test in polynomial time* - the AKS primality test - seems to have your name, except for one letter: "Agrawal", from the famous 2002 Agrawal–Kayal–Saxena primality test.
Synchronicity?
*not neccessarily useful in practice
Kind regards.
Fernando.
There is not indeed a data structure for you to query. If you have many numbers to test, you should probably run a probabilistic test since those are faster, and then follow it up with a deterministic test to make sure the number is prime. You have to know that the math behind the fastest algorithms is not for the faint of heart.
While playing around with it I created a matrix that my kids could refer to, it is a table of composites =7.
https://www.blogger.com/blogger.g?blogID=1027414910867775810#editor/target=post;postID=7708988400192086011
"best algorithm" probably is difficult to pinpoint to because many algorithms are improvements of some previously thought the best algorithm. Are you looking at complexity of the algorithm (i.e. which one requires less computation or which one requires less space) or are you just looking for an algorithm which can tell you that a particular integer is a prime the fastest?
the probability falls when the number increases, so there is still no accurate to describe it without calculating every figure, but you can use this as the first test because it reduces the universe of numbers.
https://www.researchgate.net/publication/306315418_Closing_the_universe_of_prime_numbers?ev=prf_pub
Article Closing the universe of prime numbers
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms