Abstract
A new deterministic method to determine primality of any given number is presented in this paper. The underlying principle involves the use of a special series that generates lesser prime numbers till the root of the number under scrutiny. Subsequently, divisibility is performed to check whether the number is prime or not. Such a series characteristically produces all the successive prime numbers along with a few composite numbers as well, the proportion of latter increasing as one moves to higher numbers. This technique is provably more efficient than other deterministic methods that employ division by primes till the root of the number, either by generating those smaller primes or storing them or by simply taking all odd numbers till the square root.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Saxena, N., Kayal, N.: PRIMES in P. August 6 (2002)
Conway, J.H., Guy, R.K.: The Book of Numbers, p. 130. Springer, New York (1996)
Berndt, B.C.: Ramanujan’s Theory of Prime Numbers. Ramanujan’s Notebooks, Part IV, Ch. 24. Springer, New York (1994)
Havil, J.G.: Exploring Euler’s Constant. Princeton University Press, Princeton (2003)
Khurana, U., Koul, A.: Text Compression and Searchability (forthcoming)
Koul, A., Khurana, U.: Determination Sequential Patterns in Prime Numbers. In: Proceedings of The National Conference on Bioinformatics Computing (March 2005)
Lim, C.H., Yung, M. (eds.): WISA 2004. LNCS, vol. 3325. Springer, Heidelberg (2005)
Nagell, T.: General Remarks. In: The Sieve of Eratosthenes. Introduction to Number Theory, Ch. 15, Wiley, New York (1951)
Rabin: Probabilistic Algorithms for Testing Primality. J. of Num. Th. 12, 128–138 (1980)
Solovay, S.: A fast Monte-Carlo test for Primality. SIAM. J. of Comp. 6, 84–85 (1977)
Tilborg, V.: Encyclopedia of Cryptography and Security. H.C.A (2005)
Wells, D.: The Penguin Dictionary of Curious and Interesting Numbers, Middlesex, England. Penguin Books (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khurana, U., Koul, A. (2005). Using Patterns to Generate Prime Numbers. In: Singh, S., Singh, M., Apte, C., Perner, P. (eds) Pattern Recognition and Data Mining. ICAPR 2005. Lecture Notes in Computer Science, vol 3686. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11551188_35
Download citation
DOI: https://doi.org/10.1007/11551188_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28757-5
Online ISBN: 978-3-540-28758-2
eBook Packages: Computer ScienceComputer Science (R0)