---

Mastering Nth Prime in Cairo: A Complete Guide from Zero to Hero

To find the Nth prime number in Cairo, you must implement a custom primality test function, typically called is_prime. Then, create a main function, nth, that iterates through numbers, uses is_prime to identify primes, and counts them until it finds the one at the Nth position.

You've just started your journey into Cairo, the powerhouse language for provable computation on StarkNet. You're feeling the excitement of a new frontier, but then you're hit with a classic computer science challenge: finding the Nth prime number. Suddenly, the familiar logic feels alien in this new syntax. How do you write a loop? How do you handle integers? The fear of the unknown can be a significant hurdle.

This is a common pain point for developers transitioning to a language with a unique philosophy like Cairo. But fear not. This comprehensive guide is designed to dissolve that uncertainty. We will walk you through every step, from the mathematical theory to a fully-functional, optimized Cairo implementation. By the end, you'll not only have a solution but a deeper understanding of Cairo's core mechanics, empowering you to tackle more complex problems with confidence.

---

What Exactly is the Nth Prime Problem?

The Nth Prime problem is a fundamental challenge in computational number theory. At its core, the request is simple: given a positive integer n, find the prime number that appears at the n-th position in the sequence of all prime numbers.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The sequence of prime numbers is infinite and starts like this:

• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Based on this sequence, we can easily identify the first few Nth primes:

• The 1st prime is 2.
• The 2nd prime is 3.
• The 6th prime is 13.
• The 10th prime is 29.

While the concept is straightforward, finding the 10,001st prime (which is 104,743) requires a systematic, computational approach. You can't just list them out. This is where algorithms come in, and implementing them in a language like Cairo provides an excellent exercise in mastering its syntax and logic.

---

Why Solve This Problem in Cairo?

You might wonder, "Why use a specialized language like Cairo for a classic algorithm?" The answer lies in Cairo's purpose. Cairo is not just another general-purpose programming language; it's designed to create provable programs. This is a cornerstone of the StarkNet ecosystem, a ZK-Rollup that scales Ethereum.

Every computation in a StarkNet smart contract must be provable, meaning its execution can be mathematically verified without re-executing it. Mastering algorithms like Nth Prime in Cairo builds the foundational skills needed for this new paradigm:

• Core Logic and Control Flow: This problem forces you to use fundamental building blocks like functions, loops (loop), and conditionals (if), which are the bread and butter of any program.
- Integer Handling: You'll work directly with Cairo's integer types, such as u32, and understand their limitations and capabilities. - Computational Efficiency: While our first solution will be straightforward, it opens the door to thinking about gas costs and optimization—critical concepts in the blockchain world. A more efficient algorithm translates directly to cheaper transactions. - Test-Driven Development: The Cairo ecosystem, with its built-in testing framework via Scarb, encourages a robust development process. Writing tests for our `nth` function ensures its correctness and reliability, a non-negotiable aspect of smart contract development.

By solving this problem from the kodikra Cairo 1 learning path, you are not just learning an algorithm; you are learning to think like a Cairo developer, preparing you for building complex, verifiable applications on the decentralized web.

---

How to Find the Nth Prime in Cairo: A Step-by-Step Implementation

Our strategy will be to break the problem into two manageable parts. First, we'll create a helper function to determine if a single number is prime. Second, we'll use this helper function within a main function that finds the Nth prime.

Step 1: The `is_prime` Helper Function

The foundation of our solution is the ability to test for primality. The most common method is Trial Division. The logic is as follows: to check if a number num is prime, we try to divide it by every integer from 2 up to the square root of num. If we find any number that divides num evenly (i.e., with a remainder of 0), then num is not prime. If we check all the way to its square root and find no divisors, it is prime.

Why the square root? Because if a number num has a divisor d that is larger than its square root, then it must also have a corresponding divisor num/d that is smaller than its square root. So, if we don't find a divisor by the time we reach the square root, we won't find one after.

Let's map out the logic for our is_prime function.

    ● Start: Input `num`
    │
    ▼
  ┌───────────────────┐
  │ Check `num` <= 1  │
  └─────────┬─────────┘
            │
            ├─ (Yes) ───▶ Return `false`
            │
            ▼
  ┌───────────────────┐
  │ Check `num` == 2  │
  └─────────┬─────────┘
            │
            ├─ (Yes) ───▶ Return `true`
            │
            ▼
  ┌─────────────────────────┐
  │ Check `num` is even ?   │
  └─────────┬───────────────┘
            │
            ├─ (Yes) ───▶ Return `false`
            │
            ▼
  ┌─────────────────────────────┐
  │ Loop `d` from 3 to sqrt(num)│
  │ (increment by 2)            │
  └─────────┬───────────────────┘
            │
            ▼
      ◆ `num` % `d` == 0 ?
     ╱          ╲
   (Yes)         (No)
    │             │
    ▼             ▼
Return `false`   Continue Loop
    │
    ▼
  ┌──────────────────────────────────┐
  │ If loop finishes without finding │
  │ a divisor, return `true`         │
  └──────────────────────────────────┘
    │
    ▼
    ● End

Now, let's translate this logic into Cairo code. We'll use the u32 type for our numbers.

use core::integer::{u32_sqrt};

/// Checks if a given u32 number is prime.
fn is_prime(num: u32) -> bool {
    // 1. Prime numbers must be greater than 1.
    if num <= 1 {
        return false;
    }
    
    // 2. The number 2 is the only even prime number.
    if num == 2 {
        return true;
    }

    // 3. All other even numbers are not prime. This optimization
    //    allows us to skip checking them later.
    if num % 2 == 0 {
        return false;
    }

    // 4. Calculate the limit for our trial division.
    let limit = u32_sqrt(num);
    let mut divisor: u32 = 3;
    
    // 5. Loop through odd divisors up to the square root of num.
    while divisor <= limit {
        if num % divisor == 0 {
            // Found a divisor, so it's not a prime number.
            return false;
        }
        // Move to the next odd number.
        divisor += 2;
    }
    
    // 6. If the loop completes, no divisors were found. It's prime.
    true
}

Code Walkthrough: `is_prime`

• Line 1: We import u32_sqrt from Cairo's core library to efficiently calculate the square root of a u32 integer.
• Lines 5-7: We handle the first edge case. Numbers less than or equal to 1 are not prime by definition.
• Lines 10-12: We handle the special case of 2. It's the first and only even prime.
• Lines 15-18: This is a key optimization. If a number (other than 2) is even, it's divisible by 2 and therefore not prime. By filtering these out early, our main loop can skip all even numbers.
• Line 21: We calculate the square root of num and store it in limit. Our loop will not go past this number.
• Line 22: We initialize our divisor to 3, since we've already handled 2 and all other even numbers.
• Lines 25-32: This is the main while loop. It continues as long as our divisor is less than or equal to the limit.
• Line 26: The modulo operator (%) checks for a remainder. If num % divisor is 0, we've found a factor, and we can immediately return false.
• Line 30: We increment our divisor by 2 (3, 5, 7, ...) to check only odd potential factors, another important optimization.
• Line 35: If the while loop finishes without ever finding a divisor, it means the number is prime, and we return true.

Step 2: The Main `nth` Function

With our reliable is_prime helper, we can now build the main function. The algorithm is an iterative search: we will check numbers one by one (2, 3, 4, 5, ...), use is_prime on each, and keep a count of the primes we've found. When our count matches the requested n, the number we are currently checking is our answer.

Here is the logical flow for the nth function:

    ● Start: Input `n`
    │
    ▼
  ┌──────────────────┐
  │ Check if `n == 0`│
  └────────┬─────────┘
           │
           ├─ (Yes) ───▶ Panic! (Invalid input)
           │
           ▼
  ┌──────────────────┐
  │ Check if `n == 1`│
  └────────┬─────────┘
           │
           ├─ (Yes) ───▶ Return 2
           │
           ▼
  ┌───────────────────────────────┐
  │ Initialize `count = 1`        │
  │ Initialize `candidate = 3`    │
  └──────────────┬────────────────┘
                 │
                 ▼
            ┌─────────┐
            │  Loop   │
            └────┬────┘
                 │
                 ▼
         ◆ is_prime(candidate)?
        ╱          ╲
      (Yes)         (No)
       │             │
       ▼             │
┌──────────────┐     │
│ count += 1   │     │
└──────┬───────┘     │
       │             │
       ▼             │
◆ count == n ?       │
╱          ╲         │
(Yes)         (No)   │
 │             │     │
 ▼             │     │
Return candidate     │
 │             │     │
 └─────────────┼─────┘
               │
               ▼
        ┌────────────────┐
        │ candidate += 2 │
        └────────────────┘
               │
               └─(Back to Loop)

This flow is efficient because it starts counting from the first prime (2) and then only checks odd numbers (3, 5, 7, ...) as candidates, leveraging the optimizations from our is_prime function.

Here is the complete Cairo implementation for the `nth` function:

/// Finds the nth prime number.
/// Panics if n is 0.
pub fn nth(n: u32) -> u32 {
    // 1. The problem is defined for n >= 1. The "0th" prime is not a concept.
    if n == 0 {
        panic_with_felt252('n must be greater than 0');
    }

    // 2. Handle the first prime as a quick base case.
    if n == 1 {
        return 2;
    }
    
    // 3. Initialize count to 1 because we've already accounted for the prime '2'.
    let mut count: u32 = 1; 
    // 4. Start checking for primes from the next odd number, which is 3.
    let mut candidate: u32 = 3;

    // 5. An infinite loop that we will break out of once we find the answer.
    loop {
        // 6. Use our helper function to check the current candidate.
        if is_prime(candidate) {
            // 7. If it's prime, increment our count.
            count += 1;
            // 8. Check if we have found the Nth prime.
            if count == n {
                // 9. If so, break the loop and return the candidate.
                break candidate;
            }
        }
        // 10. Move to the next odd number for the next iteration.
        candidate += 2; 
    }
}

Code Walkthrough: `nth`

• Lines 4-6: We handle the invalid input case. The problem asks for the Nth prime, which implies a 1-based index (1st, 2nd, etc.). The "0th" prime is undefined, so we panic, which will halt execution and report an error. This is good practice for invalid arguments.
• Lines 9-11: A simple optimization for the most common base case. If the user asks for the 1st prime, we immediately return 2 without any looping.
• Line 14: We initialize our count of found primes to 1. This is because we are cleverly skipping the number 2 in our loop, so we pre-count it.
• Line 16: Our candidate number starts at 3. Since we've handled 2, this is the next number we need to check.
• Line 19: Cairo's loop creates an infinite loop. The logic to exit this loop must be provided inside it, using the break keyword.
• Line 21: We call our trusty is_prime function on the current candidate.
• Lines 23-28: If is_prime returns true, we increment our count. Then, we immediately check if this new count is the n we're looking for. If it is, we use break candidate;. This special syntax in Cairo breaks the loop and makes the loop expression evaluate to the value of candidate, which is then returned by the function.
• Line 31: We increment the candidate by 2. This is a crucial optimization that ensures we only ever check odd numbers (3, 5, 7, 9, 11, ...), effectively halving the number of iterations required.

---

Where to Run and Test This Code: Your Cairo Environment

Writing the code is one thing; running and verifying it is another. The modern Cairo ecosystem revolves around Scarb, the official package manager and build tool. It simplifies creating projects, managing dependencies, compiling, and testing.

Setting Up Your Project

First, ensure you have the Cairo toolchain installed. Then, open your terminal and create a new project with Scarb:

scarb new nth_prime_project
cd nth_prime_project

This command creates a new directory called nth_prime_project with a standard file structure, including a src/lib.cairo file and a Scarb.toml configuration file.

Putting It All Together

Open the `src/lib.cairo` file and replace its contents with our complete module, including the functions and tests.

// src/lib.cairo
use core::integer::{u32_sqrt};

/// Checks if a given u32 number is prime.
fn is_prime(num: u32) -> bool {
    if num <= 1 { return false; }
    if num == 2 { return true; }
    if num % 2 == 0 { return false; }

    let limit = u32_sqrt(num);
    let mut divisor: u32 = 3;
    
    while divisor <= limit {
        if num % divisor == 0 {
            return false;
        }
        divisor += 2;
    }
    true
}

/// Finds the nth prime number.
/// Panics if n is 0.
pub fn nth(n: u32) -> u32 {
    if n == 0 {
        panic_with_felt252('n must be greater than 0');
    }
    if n == 1 {
        return 2;
    }
    
    let mut count: u32 = 1;
    let mut candidate: u32 = 3;

    loop {
        if is_prime(candidate) {
            count += 1;
            if count == n {
                break candidate;
            }
        }
        candidate += 2; 
    }
}

// Tests are essential for verifying correctness.
#[cfg(test)]
mod tests {
    use super::nth;

    #[test]
    fn test_first_prime() {
        assert(nth(1) == 2, 'first prime is 2');
    }

    #[test]
    fn test_second_prime() {
        assert(nth(2) == 3, 'second prime is 3');
    }

    #[test]
    fn test_sixth_prime() {
        assert(nth(6) == 13, 'sixth prime is 13');
    }

    #[test]
    fn test_big_prime() {
        assert(nth(10001) == 104743, '10001st prime is 104743');
    }

    #[test]
    #[should_panic]
    fn test_zero_case() {
        nth(0);
    }
}

Running the Tests

Now, from your terminal inside the `nth_prime_project` directory, run the test suite:

scarb test

If everything is correct, Scarb will compile your code and run the tests defined in the tests module. You should see an output indicating that all tests passed successfully.

$ scarb test
Testing nth_prime_project...
running 5 tests
test nth_prime_project::tests::test_first_prime ... ok
test nth_prime_project::tests::test_second_prime ... ok
test nth_prime_project::tests::test_sixth_prime ... ok
test nth_prime_project::tests::test_big_prime ... ok
test nth_prime_project::tests::test_zero_case ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 filtered out;

This confirms our logic is sound and handles all specified cases correctly, including the panic condition for n=0.

---

Performance Considerations and Alternative Approaches

The trial division method we implemented is perfectly fine for finding smaller Nth primes (like the 10,001st). However, its performance degrades as n gets very large. For each candidate prime, we are performing a loop and division operations. A more advanced and significantly faster algorithm for finding primes is the Sieve of Eratosthenes.

The Sieve works by creating a list of consecutive integers from 2 up to a certain limit. It then iteratively marks the multiples of each prime as composite (not prime), starting with the first prime, 2. The numbers that remain unmarked at the end are all the primes up to the limit.

Let's compare the two approaches.

Aspect	Trial Division (Our Implementation)	Sieve of Eratosthenes
Pros	Simple to understand and implement. Low memory usage; only needs to store a few variables. Good for checking the primality of a single, isolated number.	Extremely fast for finding all primes up to a given limit. Avoids division and square root operations in its main loop. Conceptually elegant for bulk prime generation.
Cons	Inefficient for large n due to repetitive checks. Performance scales poorly as the primes get larger.	Requires a large amount of memory to store the list (or boolean array) of numbers. More complex to implement, especially in a language like Cairo with its memory model. You must estimate an upper bound for the Nth prime beforehand.

For the scope of this kodikra module, trial division is the ideal choice as it focuses on core language features without introducing the complexities of dynamic memory allocation required for an efficient Sieve implementation in Cairo.

---

Frequently Asked Questions (FAQ)

Why does the is_prime check only go up to the square root of the number?

This is a standard mathematical optimization. If a number x has a divisor a that is greater than its square root (sqrt(x)), then it must also have a corresponding divisor b = x/a. If a > sqrt(x), then b must be less than sqrt(x). Therefore, if a divisor exists, we are guaranteed to find its smaller counterpart (or the square root itself) by the time we reach sqrt(x).

What is u32 in Cairo and why was it chosen?

u32 represents an unsigned 32-bit integer. This means it can store positive whole numbers from 0 up to 2³² - 1 (which is 4,294,967,295). This type was chosen because it's large enough to handle the test cases (like the 10,001st prime) while being computationally efficient. For even larger primes, one might need to use u64 or u128.

How would I handle very large values for n in Cairo?

For extremely large n, two things become an issue: the integer type might overflow, and the computation time will be very long. You would need to switch to a larger integer type like u64 or u128. More importantly, you would need a more advanced algorithm than trial division, such as a segmented Sieve or other probabilistic primality tests, although implementing these in Cairo is a significantly more advanced topic.

Can this Nth Prime function be used in a StarkNet smart contract?

Yes, it can. Any public function (marked with pub) in a Cairo library can be compiled into Sierra and used within a StarkNet contract. However, be mindful of gas costs. A loop that runs many times, like the one in our nth function, will consume a significant amount of gas. For on-chain use, you would only want to call it with small values of n.

What does panic_with_felt252('n must be greater than 0') do?

panic_with_felt252 is a core Cairo function that immediately halts the program's execution and signals an error. The program "panics." The argument, in this case, a short string literal, is the error message that gets returned. This is the standard way to handle unrecoverable errors or invalid function inputs in Cairo.

Why start checking for primes from the number 2?

The number 2 is the smallest and first prime number. By definition, prime numbers are natural numbers greater than 1. Therefore, the sequence must begin at 2. Our algorithm handles 2 as a special base case and then efficiently checks only odd numbers from 3 onwards.

---

Conclusion: From Theory to Provable Code

We have successfully journeyed from the theoretical definition of a prime number to a complete, tested, and optimized implementation for finding the Nth prime in Cairo. You've learned how to structure a solution by breaking it down into a helper function (is_prime) and a main function (nth), a common and powerful programming pattern.

More importantly, you've gained hands-on experience with Cairo's syntax for loops, conditionals, functions, and integer types. You've also seen the importance of optimization—by handling even numbers and using the square root limit—and the professional workflow of writing tests to guarantee your code's correctness using Scarb.

This foundational knowledge is your launchpad. As you continue your exploration of Cairo and StarkNet, these core skills will be invaluable. The world of provable computation is just beginning, and you are now equipped with the tools to build its future.

Ready for your next challenge? Continue your journey on the kodikra Cairo 1 learning path to tackle more complex problems and deepen your expertise. Or, explore more Cairo concepts and challenges on kodikra.com to broaden your understanding of this revolutionary language.

Disclaimer: This solution was developed and tested using Cairo v2.6.x and Scarb v2.6.x. The syntax and core library features may differ in past or future versions of the language.

---

Published by Kodikra — Your trusted Cairo learning resource.