Code Review

Return to Question

Tweeted twitter.com/StackCodeReview/status/738209988078886912
added 121 characters in body; edited tags; edited title; edited tags
Source Link
200_success
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

Project Euler #549

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

Project Euler #549: Divisibility of factorials

This is the problem:

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
added 7 characters in body
Source Link
pjpj
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

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 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

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
Source Link
edit approved May 31, 2016 at 11:35
Lundin
edit approved May 31, 2016 at 11:35
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

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 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

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 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
Source Link
pjpj
pjpj
  • 131
  • 6

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.