A simple primality test and the rth smallest prime factor

Daniel Panario; Bruce Richmond; Martha Yip

A simple primality test and the rth smallest prime factor

Daniel Panario
, Bruce Richmond
, Martha Yip

Mathematics

Producción científica: Conference contribution › revisión exhaustiva

Resumen

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.

Idioma original	English
Título de la publicación alojada	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics
Editores	L. Arge, G.F. Italiano, R. Sedgewick
Páginas	185-193
Número de páginas	9
Estado	Published - 2004
Evento	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States Duración: ene 10 2004 → ene 10 2004

Serie de la publicación

Nombre	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
País/Territorio	United States
Ciudad	New Orleans, LA
Período	1/10/04 → 1/10/04

Nota bibliográfica

Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

ASJC Scopus subject areas

General Engineering

Otros archivos y enlaces

Citar esto

Panario, D., Richmond, B., & Yip, M. (2004). A simple primality test and the rth smallest prime factor. En L. Arge, G. F. Italiano, & R. Sedgewick (Eds.), Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics (pp. 185-193). (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

Panario, Daniel ; Richmond, Bruce ; Yip, Martha. / A simple primality test and the rth smallest prime factor. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. editor / L. Arge ; G.F. Italiano ; R. Sedgewick. 2004. pp. 185-193 (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

@inproceedings{c9b59adbb34c48d58de54e3e524cdb6c,

title = "A simple primality test and the rth smallest prime factor",

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

author = "Daniel Panario and Bruce Richmond and Martha Yip",

note = "Copyright: Copyright 2008 Elsevier B.V., All rights reserved.; Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics ; Conference date: 10-01-2004 Through 10-01-2004",

year = "2004",

language = "English",

isbn = "0898715644",

series = "Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics",

pages = "185--193",

editor = "L. Arge and G.F. Italiano and R. Sedgewick",

booktitle = "Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics",

}

Panario, D, Richmond, B & Yip, M 2004, A simple primality test and the rth smallest prime factor. En L Arge, GF Italiano & R Sedgewick (eds.), Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics, pp. 185-193, Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics, New Orleans, LA, United States, 1/10/04.

A simple primality test and the rth smallest prime factor. / Panario, Daniel; Richmond, Bruce; Yip, Martha.
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. ed. / L. Arge; G.F. Italiano; R. Sedgewick. 2004. p. 185-193 (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

Producción científica: Conference contribution › revisión exhaustiva

TY - GEN

T1 - A simple primality test and the rth smallest prime factor

AU - Panario, Daniel

AU - Richmond, Bruce

AU - Yip, Martha

PY - 2004

Y1 - 2004

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

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

UR - https://www.scopus.com/pages/publications/8344227696

UR - https://www.scopus.com/pages/publications/8344227696#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:8344227696

SN - 0898715644

T3 - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

SP - 185

EP - 193

BT - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics

A2 - Arge, L.

A2 - Italiano, G.F.

A2 - Sedgewick, R.

T2 - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

Y2 - 10 January 2004 through 10 January 2004

ER -

Panario D, Richmond B, Yip M. A simple primality test and the rth smallest prime factor. En Arge L, Italiano GF, Sedgewick R, editores, Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. 2004. p. 185-193. (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

A simple primality test and the rth smallest prime factor

Resumen

Serie de la publicación

Conference

Nota bibliográfica

ASJC Scopus subject areas

Otros archivos y enlaces

Huella

Citar esto