Fast Prime Number Calculator

Problem Statement

Write a code that accepts integer values of rl (range low) & rh (range high) and computes the list of prime numbers in that given range and stores them in a file prime.txt. You should write a code that minimizes the overall execution time by creating multiple child processes (say n) which exploit multiple logical cores of your machine.

For a given range, say 1000 – 10000, provide the plot of n (number of processes) vs physical execution time.

Required Analysis

• (a) For varying ranges, e.g., 1000-10000; 50000-100000, etc.
• (b) For each range, run in at least 3 machines with different configurations (number of logical processors).

---

Project Structure

This repository contains two distinct implementations of the solution:

1. Man Made Project (Our Solution/)

This folder contains a manually engineered, modular C solution designed for flexibility and robustness.

• files:
  • run.c: The main entry point and interactive menu system.
  • main.c: Process manager that handles fork() and workload distribution.
  • primes.c / primes.h: Optimized prime number calculation logic.
  • plotter.py: Python script for generating performance graphs.
  • CMakeList.txt: Build configuration.

2. AI Generated Project (AI Generated/)

This folder contains a solution generated by an AI model based on the problem prompt.

• files:
  • solution.c: A single-file C implementation of the multiprocess logic.
  • auto_runner.py: Python automation script to compile the C code, run benchmarks, and generate plots.
  • prompt.txt: The original prompt used to generate the solution.

---

Prerequisites

• Operating System: Linux or WSL (Windows Subsystem for Linux) is required as the code utilizes fork() and system-specific commands (lscpu).
• Compiler: gcc (GNU Compiler Collection).
• Python: Python 3 with matplotlib library for plotting.

  sudo apt update
  sudo apt install build-essential python3-matplotlib

---

Execution Instructions

A. Running the Man Made Solution

1. Navigate to the directory:

   cd "Our Solution"

2. Compile the components:

   # Compile the worker application
   gcc main.c primes.c -o prime_app
   
   # Compile the interface
   gcc run.c -o run_interface

3. Run the interactive interface:

   ./run_interface

   • Select Option 1 to run a single benchmark and generate prime.txt.
   • Select Option 2 to run an auto-scaling test across all available cores.
   • Select Option 3 to generate the performance graph (Ensure prime_app is compiled first).

B. Running the AI Generated Solution

1. Navigate to the directory:

   cd "AI Generated"

2. Run the automation script:

   python3 auto_runner.py

   This script will:

   • Automatically compile solution.c.
   • Run benchmarks for varying numbers of processes (1 to N).
   • Generate a performance plot named ai_execution_plot.png.
   • Save found primes to ai_primes.txt.

---

Results & Outputs

Performance Plots

Both solutions provide tools to generate Number of Processes vs. Execution Time graphs.

• Man Made: Use Option 3 in ./run_interface or run python3 plotter.py.
• AI Generated: Automatically generated as ai_execution_plot.png by the runner script.

Cross-Machine Analysis

To complete the problem statement requirements:

1. Run the tests on Machine A (e.g., Laptop with 4 cores).
2. Run the tests on Machine B (e.g., Desktop with 8 cores).
3. Run the tests on Machine C (e.g., Server/VM with 2 cores).
4. Compare the resulting plots to observe scaling efficiency.

Varying Ranges

Modify the input ranges in the interface (Man Made) or edit the start_range and end_range variables in auto_runner.py (AI Generated) to test:

• Small: 1000 - 10000
• Medium: 50000 - 100000
• Large: 100000 - 500000