# Analysis of a simple factorization algorithm

- Authors
- Journal
- Theoretical Computer Science 0304-3975
- Publisher
- Elsevier
- Publication Date
- Volume
- 3
- Issue
- 3
- Identifiers
- DOI: 10.1016/0304-3975(76)90050-5
- Disciplines

## Abstract

Abstract The probability that the k th largest prime factor of a number n is at most n x is shown to approach a limit F k( x) as n → ∞. Several interesting properties of F k( x) are explored, and numerical tables are given. These results are applied to the analysis of an algorithm commonly used to find all prime factors of a given number. The average number of digits in the k th largest prime factor of a random m-digit number is shown to be asymptotically equivalent to the average length of the k th longest cycle in a permutation on m objects.

## There are no comments yet on this publication. Be the first to share your thoughts.