Posts Tagged ‘prob5’

Typical – I’m late

May 30, 2009

Here are my solutions from the last set that I never got around to posting:

Problem 3 – I guess I just printed the list and then took the biggest here.

def divisors(n):
  divs = set([1])

  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:

  return divs

def isPrime(n):
  return len(divisors(n)) == 1

divs = list(divisors(600851475143))

for div in divs:
  if isPrime(div):
    print div

Problem 4 –

def isPalidrome(num):
    numstr = str(num)
    for i in range(len(numstr)):
	if numstr[i] != numstr[-i-1]:
	    return False
    return True

i = 999
j = 999
prod = i * j
biggest = 0
big_i = 0
big_j = 0

while prod > biggest:
    while prod > biggest:
	if isPalidrome(prod):
	    biggest = prod
	    big_i = i
	    big_j = j
	j -= 1
	prod = i * j
    i -= 1
    j = i
    prod = i * j

print "Biggest is: ", big_i, " x ", big_j, " = ", biggest

Problem 5 – Okay, this one is cheap, but Carolyn and I figured out that it was super easy to just count which divisors you needed, so there wasn’t really much coding to do. 🙂

print 20*19*9*17*4*7*13*11

Problem 6 – Hmm. Don’t see where I put the source to this one, so maybe I skipped it. I’ll post it with the solutions to next (i.e. this) week’s problems.


Problem 5 and 6

May 25, 2009

Hey guys, sorry I’m late to the party. Figured I’d point out the obvious… In problem 5, we just need to calculate the product of the highest p-th power less n. (Since we’re coding, we should generalize the problem to finding the least integer divisible by all the numbers 1 to n.) I’ve got C code…

In problem 6, we can just use the formulas for sums of integers, sums of squares, and do arithmetic… Unless I’m missing something…


(Source updated after Nick (sumidiot) pointed out that I was too quick with my inequalities…)


int isPrime(int);

int main(int argc, char **argv)
int i, n;
int product = 1;
int i_power;

n = atoi(argv[1]);

for(i=2; i<=n; i++) { // For Each prime, it finds the largest power of that primes less // than n and multiplies it into the answer. if(isPrime(i)) { i_power = i; while(i_power*i <=n) { i_power = i_power*i; } product = product * i_power; printf("i_power: %d product: %d\n", i_power, product); } } printf("The smallest number divisible by 1 to %d is %d\n", n, product); return(0); } int isPrime(int a) { int i; if(a==2) return(1); if(!(a%2)) return(0); for(i = 3; i <= sqrt(a); i=i+2) { if(!(a%i)) return(0); } return(1); } [/sourcecode]