added 121 characters in body; edited tags; edited title; edited tags
200_success
• 143.2k
• 22
• 186
• 470

# Project Euler #549: Divisibility of factorials

This is the problem: https://projecteuler.net/problem=549problem. Quite:

Calculate

$$\sum_{i=2}^{10^8} s(i)$$

where $$\s(n)\$$ is the smallest $$\m\$$ such that $$\n\$$ divides $$\m!\$$.

Quite mathematical, I've found a better way than brute force by using largest prime factor and greatest common divisor. It works fine when n = 100 but still very slow when n gets larger and far too slow to solve the problem. So of course there are better ways.

Here is the code in Python:

import math

def maxPrimeFactor(n):
p = 2
while (p <= n/p):
if (n%p):
p += 1
else:
n/=p
return n

def gcd(a,b):
c = 1
while (b):
c = b
b = a % b
a = c
return a

def sn(n):
solution = prod = 1
p = maxPrimeFactor(n)
pFac = math.factorial(p)
if((pFac%n) == 0 and pFac>=n):
solution = p
else:
rest = n / gcd(pFac, n)
solution = p+1
prod = p + 1
while(prod < rest):
solution += 1
prod *= solution
while (prod % rest):
solution += 1
prod *= solution
return solution

sum = 0
for i in range(2,100000001):
sum += sn(i)
print sum


pjpj
• 131
• 6

This is the problem: https://projecteuler.net/problem=549. Quite mathematical, I've found a better way than brute force by using largest prime factor and greatest common divisor. It works fine when n = 100 but still very slow when n gets larger and far too slow to solve the problem. So of course there are better ways.

Here is the code in Python:

import math

def maxPrimeFactor(n):
p = 2
while (p <= n/p):
if (n%p):
p += 1
else:
n/=p
return n

def gcd(a,b):
c = 1
while (b):
c = b
b = a % b
a = c
return a

def sn(n):
solution = prod = 1
p = maxPrimeFactor(n)
pFac = math.factorial(p)
if((pFac%n) == 0 and pFac>=n):
solution = p
else:
rest = n / gcd(pFac, n)
solution = p+1
prod = p + 1
while(prod < rest):
solution += 1
prod *= solution
while (prod % rest):
solution += 1
prod *= solution
return solution

sum = 0
for i in range(2,100000001):
sum += sn(i)
print sum


Minor spelling
Lundin
• 4.5k
• 12
• 28

This is the problem: https://projecteuler.net/problem=549. Quite mathematical, I've found a better way than brute force by using largest prime and greatest common divisor.It It works fine when n = 100 but still very slow when n gets larger and far too slow to solve the problem. So of course there are better ways.

Here is the code in Python: How to improveit?

import math

def maxPrimeFactor(n):
p = 2
while (p <= n/p):
if (n%p):
p += 1
else:
n/=p
return n

def gcd(a,b):
c = 1
while (b):
c = b
b = a % b
a = c
return a

def sn(n):
solution = prod = 1
p = maxPrimeFactor(n)
pFac = math.factorial(p)
if((pFac%n) == 0 and pFac>=n):
solution = p
else:
rest = n / gcd(pFac, n)
solution = p+1
prod = p + 1
while(prod < rest):
solution += 1
prod *= solution
while (prod % rest):
solution += 1
prod *= solution
return solution

sum = 0
for i in range(2,100000001):
sum += sn(i)
print sum


pjpj
• 131
• 6