فرمول لژاندر، بزرگ‌ترين توان يك عدد اول (p) را پیدا می کند كه به فاكتوريل یک عدد دیگر (n) بخش پذیر است

مثال فرمول لژاندر (p = 2 و n = 27):

بنابراین 2^23 بزرگترین توان 2 است که بر 27 فاکتوریل بخش پذیر است.

این فرمول مجموع تقسیم عدد n به عدد p به توان های مختلف (گرد شده رو به پایین) را حساب می کند. توان p از 1 شروع شده و تا جایی پیش می رود که p به توان آن عدد کمتر از n شود. (در اینجا 2 به توان 5 بزرگتر از 27 است پس تا توان 4 پیش رفته است.)

برای مثال:

p = 5
n = 100

int(100/5) + int(100/25)
# 100/125 را دیگر نمی نویسیم چون 125 > 100.

p = 2
n = 128

int(128/2) + int(128/4) + int(128/8) + ... + int(128/128)

با توجه به pو n، نتیجه فرمول لژاندر را برای مثال های زیر برگردانید.

Legendre(5, 100) ➞ 24

Legendre(2, 128) ➞ 127

Legendre(3, 50) ➞ 22

نکات

• p و n اعداد صحیح مثبت خواهند بود.
• هنگامی که p بیشتر از n باشد، نتیجه باید 0 شود.