Agent Work: Prime Factors

Claude Sonnet 4.6 · COMP 321: Introduction to Computer Systems

COMP 321: Introduction to Computer Systems

Project 1: Factors

Overview

You will write C code to count the prime factors of a number. The goals of this project are as follows:

Write a small amount of C code.
Become familiar with compiling C code.
Understand the perils of writing a deeply recursive program.

Summary

You will write three versions of code to count the prime factors of a positive integer greater than one (Please remember, "1" is NOT a prime number):

Count all of the prime factors recursively. For example, 12 has 3 prime factors: 2, 2, and 3.
Count all of the prime factors iteratively.
Count the distinct prime factors iteratively. For example, 12 has 2 distinct prime factors: 2 and 3.

You will write a different procedure to handle each version. You do not need to write a particularly efficient program, although it should complete in sixty seconds on any input. In particular, a truly efficient version would use some data structure to store previously discovered primes, but you have not yet learned about data structures in C.

You will not write an entire program. We provide a basic main function to handle the I/O. First, you will write a recursive solution, but this solution might not work for certain large inputs, for example, 2,000,000,001. Second, you will write an iterative solution that is guaranteed to work for all valid inputs.

Deeply Recursive Programs

When a function is called from a C program, it is allocated memory to store its parameters and local variables. This allocation typically occurs on a region called the *program stack*. You will learn more about program stacks later in the semester.

A recursive function is one that calls itself repeatedly until some condition is satisfied. Depending on how deep the recursion is, the program stack may consume a lot of memory. Eventually the program will run out of memory and crash. For example, a very simple recursive solution to count all prime factors is likely to crash with certain large inputs, for example, 2,000,000,001. You should learn to write programs which efficiently use their stack. This is especially important if the program will be executed on a platform with limited memory, such as embedded systems or mobile phones. In this assignment, you have to write both a recursive solution (that does not have to work on all inputs) and an iterative solution that uses the stack efficiently and works for all valid inputs. A valid input is any number that can be represented by an unsigned int.

The limit command can be used to check and change the maximum stack size which can be allocated by your program. The default maximum stack size per program is 8 MB and your solution will be graded using only that default size.

Notes

The compiler generates warnings for a reason. You should fix any code that generates a warning to minimize the chances of bugs. Experienced C programmers may understand what they are doing well enough to decide that a warning is unimportant. However, code that causes warnings can be an indication of actual program errors, so it is a good idea to fix any code that causes a warning regardless of your experience level. Your code should compile without any warnings. (We will use the -Wall and -Wextra flags to cc.)

Testing is critical in all programming. You need to be sure to comprehensively test the procedures that you write.

We provide a main function that you must not change. However, when -t is specified on the command line, the function test_factors will be called with no arguments instead of running the program normally. You may put whatever testing code you would like in this function. We will not use the -t argument when grading your program, so this is solely for you to use in your testing as you see fit.

When -r is specified on the command line, the function count_factors_recursive will be called. This function should have a recursive implementation. You must not use for or while loops in its implementation. You may write helper functions, as needed, but they too must not use any loops. As previously discussed, this function does not need to handle all inputs without crashing due to stack overflow. (That said, it is fine if you are able to design an implementation that does handle all inputs without crashing).

You may also find it helpful to use some simple printf statements within your procedures to see intermediate values during the execution of your program as you are testing and debugging your code. The printf statement in C has a format string followed by a list of zero or more additional arguments. The "%" characters in the format string specify the locations in the output where the additional arguments must be printed, and the character following each "%" must match the type of the corresponding argument to printf. For example, a single unsigned integer can be printed in C using printf as follows:

``c printf("Print an unsigned int, %u, between the commas.\n", number);``

You can also learn from the other printf statements in the code given to you. Using printf statements is an effective method of debugging simple programs and for narrowing down errors in more complex programs. However, make sure that you comment out all such printf statements when you are done, as the final program should only perform the input and output that is provided in the main function.

Use requires/effects comments for each procedure, as in the provided code. These procedure comments should be about *what* the procedure does, not *how* it does it. In other words, a procedure sum might have the following effects: *Returns the sum of the elements in the array.* An inappropriate comment would be: *loops over the elements in the array using a for loop, adds each element to a running sum, and then returns the running sum after the for loop completes.* Comments inside the procedure can be used to document what the procedure is doing when the code is not relatively obvious. However, commenting the statement i += 1; with "Add one to i." is pointless. It is only adding clutter to your program.

When you are modifying an existing program, *the first and foremost rule of good coding style* is that the style of your code, e.g., its indentation, should match the style of the surrounding code. In effect, it should not be obvious to a reader where different people have edited the code. Also, keep in mind that if you consistently indent your code, it will make it easier for someone else to understand your code.

Files

You should see the following files in your workspace:

factors.c - provided code (implement your solution here)
Makefile - specification for building factors using make
writeup.md - a skeleton writeup file
instructions.md - this file

Compiling and Running Your Code

To compile your code, use the Unix command:

make

This will compile your code producing an executable file named factors. This file can then be run to determine the number of prime factors of 12 as follows:

./factors
Enter number:
12
12 has 3 prime factors, 2 of them distinct.

Since a prime number's only prime factor is the number itself, inputting a prime number, such as 13, should produce output like:

13 has 1 prime factors, 1 of them distinct.

Make sure that the iterative version of your program works for all valid inputs. However, the recursive version of your program may crash with large inputs. For example, on executing the recursive solution to count all prime factors with input 2,000,000,001, the following will likely occur:

./factors -r
Enter number:
2000000001
Segmentation fault (core dumped)

Your program must only handle valid inputs. If an invalid input is given to your program, it is acceptable for your program to output nonsense. In addition, it is acceptable for the recursive version of your program to crash due to stack overflow on large valid inputs.

Testing

Use the grade tool to run the automated test suite:

# From the workspace directory
bin/grade .

# Or specify the workspace path
bin/grade ./workspaces/agent_factors

The grade tool will compile your code and run all tests, showing which pass and fail. Focus on getting all tests to pass.

--- *COMP 321: Introduction to Computer Systems, Rice University, Spring 2024*

factors.c3.8 KB

/*
 * COMP 321 Project 1: Factors
 *
 * This program computes the number of prime factors, and optionally the number
 * of distinct prime factors, for an unsigned integer input.
 * 
 * <Put your name and NetID here>
 */

#include <assert.h>
#include <math.h>     // Included in case you use the standard math library.
#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>

static unsigned int	count_distinct_factors(unsigned int n);
static unsigned int	count_factors(unsigned int n);
static unsigned int	count_factors_recursive(unsigned int n);
static void		test_factors(void);

// Replace this comment with any global variable declarations.

// Replace this comment with any helper functions.
  
/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of factors of the input "n".
 */
static unsigned int
count_factors_recursive(unsigned int n)
{
	// Replace this comment with your local variable declarations.
    
	assert(n > 1);
	/*
	 * Replace this comment with your code.
	 */
	return (0);
}

/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of factors of the input "n".
 */
static unsigned int
count_factors(unsigned int n)
{
	// Replace this comment with your local variable declarations.
    
	assert(n > 1);
	/*
	 * Replace this comment with your code. 
	 */
	return (0);
}

/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of distinct factors of the input "n".
 */
static unsigned int
count_distinct_factors(unsigned int n)
{
	// Replace this comment with your local variable declarations.

	assert(n > 1);
	/*
	 * Replace this comment with your code.  Also, don't forget to modify
	 * the following statement to return the actual number of distinct
	 * factors.
	 */
	return (0);
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   Runs testing procedures.  Currently only prints a message.
 */
static void
test_factors(void)
{

	printf("Test Factors\n");
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   If the "-t" option is specified on the command line, then test code is
 *   executed and the program exits.
 *   
 *   Otherwise, requests a number from standard input.  If the "-r" option is
 *   specified on the command line, then prints the number of prime factors
 *   that the input number has, calculated using a recursive function.
 *   Otherwise, prints the number of prime factors that the input number has
 *   and the number of those factors that are distinct using iterative
 *   functions.
 *
 *   Upon completion, the program always returns 0.
 *
 *   If the number that is input is not between 2 and the largest unsigned
 *   integer, the output of the program is undefined, but it will not crash.
 */
int
main(int argc, char **argv)
{
	unsigned int n;
	int c;
	bool recursive = false;
	bool runtests = false;

	// Parse the command line.
	while ((c = getopt(argc, argv, "rt")) != -1) {
		switch (c) {
		case 'r':             // Use recursive version.
			recursive = true;
			break;
		case 't':             // Run test procedure and exit.
			runtests = true;
			break;
		default:
			break;
		}
	}

	// If "-t" is specified, run test procedure and exit program.
	if (runtests) {
		test_factors();
		return (0);
	}

	// Get input.
	printf("Enter number:\n");
	if (scanf("%u", &n) != 1) {
		fprintf(stderr, "Input error\n");
		return (1);
	}

	// Validate the input.
	if (n < 2) {
		fprintf(stderr, "Invalid input: %u\n", n);
		return (1);
	}

	// Print results.
	if (recursive) {
		// Use recursive version.
		printf("%u has %u prime factors.\n",
		    n, count_factors_recursive(n));
	} else {
		// Use iterative versions.
		printf("%u has %u prime factors, %u of them distinct.\n",
		    n, count_factors(n), count_distinct_factors(n));
	}

	// Report no errors.
	return (0);
}

factors.c3.8 KB

/*
 * COMP 321 Project 1: Factors
 *
 * This program computes the number of prime factors, and optionally the number
 * of distinct prime factors, for an unsigned integer input.
 * 
 * <Put your name and NetID here>
 */

#include <assert.h>
#include <math.h>     // Included in case you use the standard math library.
#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>

static unsigned int	count_distinct_factors(unsigned int n);
static unsigned int	count_factors(unsigned int n);
static unsigned int	count_factors_recursive(unsigned int n);
static void		test_factors(void);

// Replace this comment with any global variable declarations.

// Replace this comment with any helper functions.
  
/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of factors of the input "n".
 */
static unsigned int
count_factors_recursive(unsigned int n)
{
	// Replace this comment with your local variable declarations.
    
	assert(n > 1);
	/*
	 * Replace this comment with your code.
	 */
	return (0);
}

/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of factors of the input "n".
 */
static unsigned int
count_factors(unsigned int n)
{
	// Replace this comment with your local variable declarations.
    
	assert(n > 1);
	/*
	 * Replace this comment with your code. 
	 */
	return (0);
}

/* 
 * Requires:  
 *   The input "n" must be greater than 1.
 *
 * Effects: 
 *   Returns the number of distinct factors of the input "n".
 */
static unsigned int
count_distinct_factors(unsigned int n)
{
	// Replace this comment with your local variable declarations.

	assert(n > 1);
	/*
	 * Replace this comment with your code.  Also, don't forget to modify
	 * the following statement to return the actual number of distinct
	 * factors.
	 */
	return (0);
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   Runs testing procedures.  Currently only prints a message.
 */
static void
test_factors(void)
{

	printf("Test Factors\n");
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   If the "-t" option is specified on the command line, then test code is
 *   executed and the program exits.
 *   
 *   Otherwise, requests a number from standard input.  If the "-r" option is
 *   specified on the command line, then prints the number of prime factors
 *   that the input number has, calculated using a recursive function.
 *   Otherwise, prints the number of prime factors that the input number has
 *   and the number of those factors that are distinct using iterative
 *   functions.
 *
 *   Upon completion, the program always returns 0.
 *
 *   If the number that is input is not between 2 and the largest unsigned
 *   integer, the output of the program is undefined, but it will not crash.
 */
int
main(int argc, char **argv)
{
	unsigned int n;
	int c;
	bool recursive = false;
	bool runtests = false;

	// Parse the command line.
	while ((c = getopt(argc, argv, "rt")) != -1) {
		switch (c) {
		case 'r':             // Use recursive version.
			recursive = true;
			break;
		case 't':             // Run test procedure and exit.
			runtests = true;
			break;
		default:
			break;
		}
	}

	// If "-t" is specified, run test procedure and exit program.
	if (runtests) {
		test_factors();
		return (0);
	}

	// Get input.
	printf("Enter number:\n");
	if (scanf("%u", &n) != 1) {
		fprintf(stderr, "Input error\n");
		return (1);
	}

	// Validate the input.
	if (n < 2) {
		fprintf(stderr, "Invalid input: %u\n", n);
		return (1);
	}

	// Print results.
	if (recursive) {
		// Use recursive version.
		printf("%u has %u prime factors.\n",
		    n, count_factors_recursive(n));
	} else {
		// Use iterative versions.
		printf("%u has %u prime factors, %u of them distinct.\n",
		    n, count_factors(n), count_distinct_factors(n));
	}

	// Report no errors.
	return (0);
}

factors.c4.2 KB

/*
 * COMP 321 Project 1: Factors
 *
 * This program computes the number of prime factors, and optionally the number
 * of distinct prime factors, for an unsigned integer input.
 * 
 * <Put your name and NetID here>
 */

#include <assert.h>
#include <math.h>     // Included in case you use the standard math library.
#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>

static unsigned int	count_distinct_factors(unsigned int n);
static unsigned int	count_factors(unsigned int n);
static unsigned int	count_factors_recursive(unsigned int n);
static void		test_factors(void);

// Replace this comment with any global variable declarations.

/*
 * Requires:
 *   n >= 2, d >= 2.
 *
 * Effects:
 *   Returns the number of prime factors of n, testing divisibility starting
 *   from d.
 */
static unsigned int
count_factors_recursive_helper(unsigned int n, unsigned int d)
{

	if (d * d > n)
		return (1);
	if (n % d == 0)
		return (1 + count_factors_recursive_helper(n / d, d));
	return (count_factors_recursive_helper(n, d + 1));
}

/*
 * Requires:
 *   The input "n" must be greater than 1.
 *
 * Effects:
 *   Returns the number of prime factors of the input "n", counted with
 *   multiplicity, using a recursive implementation.
 */
static unsigned int
count_factors_recursive(unsigned int n)
{
	assert(n > 1);
	return (count_factors_recursive_helper(n, 2));
}

/*
 * Requires:
 *   The input "n" must be greater than 1.
 *
 * Effects:
 *   Returns the number of prime factors of the input "n", counted with
 *   multiplicity, using an iterative implementation.
 */
static unsigned int
count_factors(unsigned int n)
{
	unsigned int count = 0;
	unsigned int d;

	assert(n > 1);
	for (d = 2; d * d <= n; d++) {
		while (n % d == 0) {
			count++;
			n /= d;
		}
	}
	if (n > 1)
		count++;
	return (count);
}

/*
 * Requires:
 *   The input "n" must be greater than 1.
 *
 * Effects:
 *   Returns the number of distinct prime factors of the input "n", using
 *   an iterative implementation.
 */
static unsigned int
count_distinct_factors(unsigned int n)
{
	unsigned int count = 0;
	unsigned int d;

	assert(n > 1);
	for (d = 2; d * d <= n; d++) {
		if (n % d == 0) {
			count++;
			while (n % d == 0)
				n /= d;
		}
	}
	if (n > 1)
		count++;
	return (count);
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   Runs testing procedures.  Currently only prints a message.
 */
static void
test_factors(void)
{

	printf("Test Factors\n");
}

/* 
 * Requires:
 *   Nothing.
 *
 * Effects:
 *   If the "-t" option is specified on the command line, then test code is
 *   executed and the program exits.
 *   
 *   Otherwise, requests a number from standard input.  If the "-r" option is
 *   specified on the command line, then prints the number of prime factors
 *   that the input number has, calculated using a recursive function.
 *   Otherwise, prints the number of prime factors that the input number has
 *   and the number of those factors that are distinct using iterative
 *   functions.
 *
 *   Upon completion, the program always returns 0.
 *
 *   If the number that is input is not between 2 and the largest unsigned
 *   integer, the output of the program is undefined, but it will not crash.
 */
int
main(int argc, char **argv)
{
	unsigned int n;
	int c;
	bool recursive = false;
	bool runtests = false;

	// Parse the command line.
	while ((c = getopt(argc, argv, "rt")) != -1) {
		switch (c) {
		case 'r':             // Use recursive version.
			recursive = true;
			break;
		case 't':             // Run test procedure and exit.
			runtests = true;
			break;
		default:
			break;
		}
	}

	// If "-t" is specified, run test procedure and exit program.
	if (runtests) {
		test_factors();
		return (0);
	}

	// Get input.
	printf("Enter number:\n");
	if (scanf("%u", &n) != 1) {
		fprintf(stderr, "Input error\n");
		return (1);
	}

	// Validate the input.
	if (n < 2) {
		fprintf(stderr, "Invalid input: %u\n", n);
		return (1);
	}

	// Print results.
	if (recursive) {
		// Use recursive version.
		printf("%u has %u prime factors.\n",
		    n, count_factors_recursive(n));
	} else {
		// Use iterative versions.
		printf("%u has %u prime factors, %u of them distinct.\n",
		    n, count_factors(n), count_distinct_factors(n));
	}

	// Report no errors.
	return (0);
}

Section: Testing Strategy

Score: 3/3 points

Assessment:

What was provided: The student describes an incremental testing approach using the grade tool, with specific test cases organized by category: simple base cases (n=2, n=4, n=12), large primes (4294967291), highly composite numbers (510510 = 2×3×5×7×11×13×17), and verification of both recursive and iterative implementations.

Strengths:

Provides concrete, specific examples with expected factor counts (e.g., n=12 → 3 factors, 2 distinct)
Tests near the boundary of unsigned int (4294967291 is close to UINT_MAX = 4294967295, and is in fact a large prime)
Includes a highly composite number (510510) with its full factorization to verify correctness on numbers with many distinct prime factors
Explicitly mentions testing both recursive and iterative implementations and their respective domains of correctness
Demonstrates a systematic progression from simple to complex inputs

Errors/Gaps:

Does not explicitly mention n=1 (not a prime, zero factors), which is an important edge case
Does not explicitly mention powers of 2 (single prime factor, multiple occurrences) as a test category

Detailed Feedback: This is a strong testing strategy. The student provides specific numeric examples with expected outputs, covers normal cases (small composites and primes), edge cases (large primes, highly composite numbers), and boundary conditions (near UINT_MAX). The mention of testing both recursive and iterative implementations addresses the comparison testing criterion. While n=1 and pure powers of 2 aren't explicitly listed, the overall coverage and specificity of the examples meet the standard for full credit.

Rubric Breakdown:

Systematic approach with specific examples: 1/1 — Clear progression from base cases to complex inputs with concrete numbers
Edge and boundary cases: 1/1 — Large primes near UINT_MAX and highly composite numbers covered
Testing both implementations: 1/1 — Explicitly verifies recursive for moderate inputs and iterative for all valid inputs

---

Section: Something I Learned

Score: 2/2 points

Assessment:

What was provided: The student describes the static keyword applied to functions in C, explaining that it limits linkage to the current translation unit, prevents name collisions, and serves as a form of encapsulation analogous to "private" functions.

Strengths:

Identifies a specific, well-defined C feature (the static storage-class specifier on functions)
Demonstrates accurate technical understanding: correctly describes file-scope linkage, translation unit visibility, and linker behavior
Connects the feature to a practical idiom (C's equivalent of private helper functions)
Uses precise systems terminology ("translation unit," "linkage," "linker")

Errors/Gaps:

None — the explanation is technically accurate and clearly articulated

Detailed Feedback: This is an excellent answer that demonstrates genuine learning about a C language feature that goes beyond basic assignment requirements. The student accurately explains that static on a function restricts its linkage to internal (file-scope), preventing the symbol from being exported to the linker. The connection to encapsulation patterns shows deeper systems understanding. This is a valid C feature that is typically not the focus of introductory lectures.

Rubric Breakdown:

Identifies a specific C feature: 1/1 — static for file-scope functions is a legitimate C-specific feature
Demonstrates understanding: 1/1 — Accurate explanation of linkage, translation units, and practical motivation

---

Overall Summary

Section	Score	Notes
Testing Strategy	3/3	Systematic, specific examples covering normal/edge/boundary cases and both implementations
Something I Learned	2/2	Clear, accurate explanation of `static` linkage for functions
Total	5/5

General Comments:

This is an excellent submission. The testing strategy is thorough and concrete, with well-chosen test values that probe important boundaries of the problem (near UINT_MAX, highly composite numbers, primes). The "Something I Learned" response demonstrates strong systems-level understanding of C's linkage model and uses precise terminology. The student clearly engaged deeply with both the implementation and the language features encountered during the project.

Total: 5/5

.mcp.json

diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index fc55b2a..0000000
--- a/.mcp.json
+++ /dev/null
@@ -1,11 +0,0 @@
-{
-  "mcpServers": {
-    "bscs-bench": {
-      "command": "/Users/bebe/Code/bscs-bench/bin/bscs-mcp",
-      "args": [
-        "--workspace",
-        "./lib b/lib
index af4ebc4..7620d8e 120000
--- a/lib
+++ b/lib
@@ -1 +1 @@
-/Users/bebe/Code/bscs-bench/comp321/lib
\ No newline at end of file
+/opt/csapp
\ No newline at end of file

writeup.md

diff --git a/writeup.md b/writeup.md
index d387eed..af8b0d1 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,10 +1,10 @@
 # COMP 321 Project 1: Factors
 
 ## Student Information
-[Replace with your name and NetID.]
+Student, NetID
 
 ## Testing Strategy
-[Replace with a detailed description of your testing strategy.]
+I tested each function incrementally using the provided grade tool. I started with simple base cases: n=2 (a prime, should return 1 factor), n=4 (2*2, should return 2 factors with 1 distinct), and n=12 (2*2*3, should return 3 factors with 2 distinct). I then tested with larger numbers including large primes (e.g., 4294967291) and highly composite numbers (e.g., 510510 = 2*3*5*7*11*13*17) to verify correctness near the bounds of unsigned int. For the recursive function, I verified it worked for moderate inputs and that the iterative version handled all valid inputs correctly.
 
 ## Something I Learned
-[Replace with a description of one feature of C that you learned while completing this assignment that wasn't taught in lecture or lab.]
+I learned about the use of `static` for file-scope functions in C. The `static` keyword applied to a function limits its linkage to the current translation unit (source file), which prevents name collisions with functions of the same name in other files and serves as a form of encapsulation. This is a common C idiom for "private" helper functions that the linker will not export to other modules.

Agent Work: Prime Factors

COMP 321: Introduction to Computer Systems

Project 1: Factors

Overview

Summary

Deeply Recursive Programs

Notes

Files

Compiling and Running Your Code

Testing

COMP 321 Project 1: Factors

Student Information

Testing Strategy

Something I Learned

Section: Testing Strategy

Score: 3/3 points

Assessment:

Rubric Breakdown:

Section: Something I Learned

Score: 2/2 points

Assessment:

Rubric Breakdown:

Overall Summary

General Comments:

Sub-Model Usage