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…

Jimbo

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

#include

#include

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]

### Like this:

Like Loading...

*Related*

Tags: Jimbo, jnh, prob5, prob6

This entry was posted on May 25, 2009 at 6:53 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

May 25, 2009 at 8:46 pm |

c huh? I haven’t compiled such a program in a while (who knew you had to link to the math library with -lm?). For practice, I may take the ideas of your code and rig it up in python. Should be fun.

Also, welcome, and no worries about the late start. You’re not the only one. When you post a solution, or comments, or anything, it’d probably helpful to tag it, e.g., with ‘prob5’ and perhaps (though perhaps not as useful) ‘jnh’. That’ll let us easily pull up all the solutions to a single problem, or see all the solutions by any author.

May 25, 2009 at 9:45 pm |

Perhaps I’m mistaken, but shouldn’t your while loop, to find powers, be using <= for comparison, instead of < ? It seems like this fails to include the upper bound if it is a prime power.

May 26, 2009 at 12:03 am |

Thanks for noting the tags. I thought I had added them, but I haven’t learned wordpress quite yet…

Good catch on the inequality. The previous code would be off by a power of p for an input of p^n. Oops… haven’t coded in awhile.

May 28, 2009 at 1:28 am |

I like this solution. It’s much quicker than computing the lcm (which has the benefit of being fairly trivial to code). It hadn’t occured to me that the lcm over a range will only change at prime powers. I don’t know much about the c math library, but if it’s got a ln function (how could it not?), you can get rid of your inner while loop completely, just calculate the power of each prime directly.