prime-sieve-generator
npx machina-cli add skill a5c-ai/babysitter/prime-sieve-generator --openclawFiles (1)
SKILL.md
1.7 KB
Prime Sieve Generator Skill
Purpose
Generate optimized prime sieves and factorization routines for various competitive programming scenarios.
Capabilities
- Sieve of Eratosthenes (segmented, linear)
- Smallest prime factor sieve
- Miller-Rabin primality testing
- Pollard's rho factorization
- Precompute prime-related values
- Generate primes in range
Target Processes
- prime-algorithms
- number-theory-algorithms
- combinatorics-counting
Sieve Variants
Basic Sieves
- Sieve of Eratosthenes O(n log log n)
- Linear sieve O(n)
- Segmented sieve (for large ranges)
Factorization Sieves
- Smallest prime factor (SPF) sieve
- Mobius function sieve
- Euler's totient sieve
Primality Testing
- Miller-Rabin (deterministic for small n)
- Fermat test
- Trial division
Factorization
- Trial division O(sqrt(n))
- Pollard's rho O(n^1/4)
- Using SPF sieve O(log n)
Input Schema
{
"type": "object",
"properties": {
"type": {
"type": "string",
"enum": ["sieve", "primalityTest", "factorization", "spfSieve"]
},
"limit": { "type": "integer" },
"optimizations": { "type": "array" },
"language": {
"type": "string",
"enum": ["cpp", "python", "java"]
}
},
"required": ["type"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"code": { "type": "string" },
"complexity": { "type": "object" },
"memoryUsage": { "type": "string" }
},
"required": ["success", "code"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/prime-sieve-generator/SKILL.mdView on GitHub Overview
Generates optimized prime sieves and factorization routines for competitive programming. It covers segmented and linear sieves, SPF sieve, Miller-Rabin primality testing, Pollard's Rho factorization, and precomputation of prime-related values.
How This Skill Works
The skill offers modular implementations for sieves and factorization that can be configured via inputs. It supports basic, segmented, and linear sieves, as well as SPF, Mobius, and Euler's totient precomputations, enabling fast primality tests and factoring across ranges.
When to Use It
- Generate primes up to a large n with a segmented sieve
- Factor many numbers quickly using an SPF sieve
- Test primality deterministically for small to medium n (Miller-Rabin)
- Factorize composites with Pollard's Rho when trial division is slow
- Precompute Mobius, Euler's totient, or other prime-related values for fast queries
Quick Start
- Step 1: Choose a sieve type and set your limit (segmented for large ranges or linear for speed)
- Step 2: Enable SPF, Mobius, or Euler totient precomputation and generate primes in range
- Step 3: Run Miller-Rabin for primality tests or Pollard's Rho for factorization, reusing cached results
Best Practices
- Choose sieve variant based on limit: segmented for large ranges, linear for dense ranges
- Use SPF sieve when fast factorization or Möbius/totient values are needed
- Precompute primes in the target range before answering queries
- Combine trial division with Miller-Rabin for robust primality checks
- Cache results and reuse across multiple test cases to save time
Example Use Cases
- Find all primes up to 1e7 using a linear sieve
- Factorize a list of numbers up to 1e12 with Pollard's Rho and SPF support
- Count prime factors across a range using SPF and Euler's totient sieve
- Deterministic Miller-Rabin primality test for 32-bit integers
- Generate primes in [L, R] using a segmented sieve for large ranges
Frequently Asked Questions
Add this skill to your agents
