Problem 5 and 6

by

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]

Advertisements

Tags: , , ,

4 Responses to “Problem 5 and 6”

  1. sumidiot Says:

    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.

  2. sumidiot Says:

    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.

  3. jnh5y Says:

    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.

  4. sumidiot Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: