Abstract
We analyze the classical primality test from high school. This analysis requires information on the first smallest prime factor of an integer. We also provide asymptotic formulas for the average value of the logarithm of the rth smallest prime factor, averaged over the first N integers. Our results are analogous to the ones for the rth smallest size of components in random decomposable combinatorial structures and extend works by de Bruijn and others. The results also show the strong connection between decomposition of combinatorial objects and prime decomposition of integer numbers.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics |
| Editors | L. Arge, G.F. Italiano, R. Sedgewick |
| Pages | 185-193 |
| Number of pages | 9 |
| State | Published - 2004 |
| Event | Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States Duration: Jan 10 2004 → Jan 10 2004 |
Publication series
| Name | Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics |
|---|
Conference
| Conference | Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics |
|---|---|
| Country/Territory | United States |
| City | New Orleans, LA |
| Period | 1/10/04 → 1/10/04 |
Bibliographical note
Copyright:Copyright 2008 Elsevier B.V., All rights reserved.
ASJC Scopus subject areas
- Engineering (all)