This site is supported by donations to The OEIS Foundation.

Least prime factor of n

(Redirected from Smallest prime factor)

Percentage of integers with lpf (n) = p.

lpf = 2 (50%)
lpf = 3 (16.666666666667%)
lpf = 5 (6.6666666666667%)
lpf = 7 (3.8095238095238%)
lpf = 11 (2.0779220779221%)
lpf = 13 (1.5984015984016%)
lpf = 17 (1.1282834812247%)
lpf = 19 (0.9501334578734%)
lpf = 23 (0.74358270616179%)
lpf = 29 (0.56409722536412%)
lpf = 31 (0.50950717129662%)
lpf = 37 (0.41311392267294%)
lpf = 41 (0.3627341760055%)
lpf = 43 (0.33742714047024%)
lpf   ≥   47 (14.17193989975%)
The least prime factor of an integer
 n
is the smallest prime number that divides the number. For example, the least prime factor of 945 is 3. The least prime factor of all even numbers is 2. A prime number is its own least prime factor (as well as its own greatest prime factor).

By convention, 1 is given as its own least prime factor, but of course this has met with objections. By disallowing 1 as a prime number, we can then say that each prime number is its own least and greatest prime factor. However, in the OEIS, it is reasonable to believe that some users will look up the sequence of least prime factors as “1, 2, 3, 2, 5, 2, 7, 2, 3, 2 ” (give or take a few terms), and that should deliver a result.

Smallest prime dividing
 n, n   ≥   2
. (See A020639 Lpf (n): Least prime dividing n, with
 a (1) = 1
.)

{2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2, 31, 2, 3, 2, 5, 2, 37, 2, 3, 2, 41, 2, 43, 2, 3, 2, 47, 2, 7, 2, 3, 2, 53, 2, 5, 2, 3, 2, 59, 2, ...}

Density of integers with smallest prime factor prime (n)

The density of positive integers with smallest prime factor prime (n) is

{
 1 2
,
 1 6
,
 1 15
,
 4 105
,
 8 385
,
 16 1001
,
 192 17017
,
 3072 323323
,
 55296 7436429
, ...} =
{1 −
 1 2
,
 1 2
 1 3
,
 1 3
 4 15
,
 4 15
 8 35
, ...}

where

{1,
 1 2
,
 1 3
,
 4 15
,
 8 35
,
 16 77
,
 192 1001
,
 3072 17017
,
 55296 323323
, ...} =
{1, 1 −
 1 2
, 1 −
 1 2
 1 6
, 1 −
 1 2
 1 6
 1 15
, 1 −
 1 2
 1 6
 1 15
 4 105
, 1 −
 1 2
 1 6
 1 15
 4 105
 8 385
, ...}

is the density of prime (n)-rough numbers.

The density of positive integers with smallest prime factor prime (n) is equal to the density of prime (n)-rough numbers minus the density of prime (n + 1)-rough numbers.

A038110 Numerator of
 n  − 1

 k  = 1
(1  −
 1 prime (k )
)
. Numerator of density of integers with smallest prime factor prime (n). Numerator of density of prime (n)-rough numbers.

{1, 1, 1, 4, 8, 16, 192, 3072, 55296, 110592, 442368, 13271040, 477757440, 19110297600, 802632499200, 1605264998400, 6421059993600, 12842119987200, 770527199232000, 50854795149312000, 3559835660451840000, ...}

A038111 Denominator of
 1 prime (n)
 n  − 1

 k  = 1
(1  −
 1 prime (k )
)
. a (n) = A060753 (n)  ⋅  prime (n). Denominator of density of integers with smallest prime factor prime (n).

{2, 6, 15, 105, 385, 1001, 17017, 323323, 7436429, 19605131, 86822723, 3212440751, 131710070791, 5663533044013, 266186053068611, 613385252723321, 2783825377744303, 5855632691117327, 392327390304860909, ...}

A060753 Denominator of
 n  − 1

 k  = 1
(1  −
 1 prime (k )
)
. a (n) = A038111 (n)  / prime (n). Denominator of density of prime (n)-rough numbers.

{1, 2, 3, 15, 35, 77, 1001, 17017, 323323, 676039, 2800733, 86822723, 3212440751, 131710070791, 5663533044013, 11573306655157, 47183480978717, 95993978542907, 5855632691117327, 392327390304860909, ...}