mi blag

a couple more

Tiempo de lectura estimada: 2 minutos

Víctor Jáquez

''I'm no so proud about this. The eratosthenes function is almost a copy&paste''

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from math import sqrt
def eratosthenes (limit):
    D = {} # map composite integers to primes witnessing their compositeness
    q = 2  # first integer to test for primality
    while q <= limit:
        if q not in D:
            yield q       # not marked composite, must be prime
            D[q * q] = [q]  # first multiple of q not already marked
         else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault (p + q, []).append (p)
            del D[q]       # no longer need D[q], free memory
         q += 1
 num = 600851475143
 print max (filter (lambda x: num % x == 0, eratosthenes (int (sqrt (num)) + 1)))

''At least I learned a bit more about the prime test and the Eratosthenes sieve''

''I suspect this one can be more efficient''

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

1
2
f = lambda x: x == x[::-1]
print max ([ (a * b) for a in xrange (100, 1000) for b in xrange (a, 1000) if f (str (a * b)) ])