A simple primality test and the rth smallest prime factor

Daniel Panario, Bruce Richmond, Martha Yip

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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 languageEnglish
Title of host publicationProceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics
EditorsL. Arge, G.F. Italiano, R. Sedgewick
Pages185-193
Number of pages9
StatePublished - 2004
EventProceedings 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 2004Jan 10 2004

Publication series

NameProceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

Conference

ConferenceProceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics
Country/TerritoryUnited States
CityNew Orleans, LA
Period1/10/041/10/04

Bibliographical note

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

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'A simple primality test and the rth smallest prime factor'. Together they form a unique fingerprint.

Cite this