سؤالات چالش برانگیز
- خانه
- /
- سؤالات چالش برانگیز
- /
- بزرگترین عامل اول<
بزرگترین عامل اول
هر عدد طبیعی از حاصلضرب تعدادی عدد اول ساخته شده است (غیر از 1). مثلا عدد 70 از حاصلضرب 2 و 5 و 7 ساخته شده است. بنابراین بزرگترین عامل اول 70 عدد 7 است.
سؤال: بزرگترین عامل اول عدد 600851475143 را حساب کنید.
راه اول:
n = 600851475143
i = 2
while i <= n:
if n % i == 0:
if n == i:
print(n)
n = n // i
else:
i = i + 1راه دوم:
n = 600851475143
p = 2
greatest_factor = 1
while n > 1:
if n % p == 0:
greatest_factor = p
n = n // p
while n % p == 0:
n = n // p
p = p + 1
print(greatest_factor)راه سوم: این راه طولانیتر است.
def is_prime(primes: list, n: int):
result = True
for prime in primes:
if n % prime == 0:
return False
return result
def largest_prime_factor(n: int):
primes = []
q = n
for i in range(2, q):
if q % i == 0:
if q == i:
return i
q = q // i
if is_prime(primes, i):
primes.append(i)
else:
continue
if primes:
return(primes[-1])
else:
return(n)
print(largest_prime_factor(600851475143))جواب نهایی: 6857
- برچسب ها
0 نظر