Legendre,s Formula
المؤلف:
Séroul, R.
المصدر:
Legendre,s Formula" and "Implementation of Legendre,s Formula." §8.7.1 and 8.7.2 in Programming for Mathematicians. Berlin: Springer-Verlag
الجزء والصفحة:
pp. 175-179
25-8-2020
843
Legendre's Formula
Legendre's formula counts the number of positive integers less than or equal to a number 
which are not divisible by any of the first 
primes,
 |
(1)
|
where 
is the floor function. Taking 
, where 
is the prime counting function, gives
 |
(2)
|
Legendre's formula holds since one more than the number of primes in a range equals the number of integers minus the number of composites in the interval.
Legendre's formula satisfies the recurrence relation
 |
(3)
|
Let 
, then
where 
is the totient function, and
 |
(9)
|
where 
. If 
, then
 |
(10)
|
Note that 
is not practical for computing 
for large arguments. A more efficient modification is Meissel's formula.
REFERENCES:
Séroul, R. "Legendre's Formula" and "Implementation of Legendre's Formula." §8.7.1 and 8.7.2 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-179, 2000.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
