Exercism - Nth Prime

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

ArgumentError and Exception Handling

ArgumentError is thrown when a function receives an invalid argument. You can throw it to indicate that the input doesn’t meet the function’s requirements.

void main() {
  int findPrime(int n) {
    if (n < 1) {
      throw ArgumentError('There is no zeroth prime');
    }
    // Find prime logic...
    return 0;
  }
  
  try {
    findPrime(0); // Throws ArgumentError
  } catch (e) {
    print(e); // ArgumentError: There is no zeroth prime
  }
}

Lists

Lists are ordered collections of items. You can add elements, check the length, and access the last element.

void main() {
  // Create list with initial element
  List<int> primes = [2];
  
  // Add elements
  primes.add(3);
  primes.add(5);
  print(primes); // [2, 3, 5]
  
  // Check length
  print(primes.length); // 3
  
  // Get last element
  print(primes.last); // 5
  
  // Check if we have enough primes
  int n = 5;
  while (primes.length < n) {
    // Find next prime and add it
    primes.add(7);
  }
}

While Loops

While loops repeatedly execute a block of code as long as a condition is true. They’re perfect for processes that continue until a specific condition is met.

void main() {
  List<int> primes = [2];
  int n = 5;
  int candidate = 3;
  
  // Continue until we have n primes
  while (primes.length < n) {
    // Check if candidate is prime
    if (isPrime(candidate)) {
      primes.add(candidate);
    }
    candidate += 2; // Skip even numbers
  }
  
  print(primes.last); // The nth prime
}

Modulo Operator

The modulo operator (%) returns the remainder of a division operation. It’s essential for checking divisibility.

void main() {
  int number = 15;
  
  // Check if divisible by a prime
  print(15 % 3); // 0 (15 is divisible by 3)
  print(15 % 5); // 0 (15 is divisible by 5)
  print(15 % 7); // 1 (15 is not divisible by 7)
  
  // Check divisibility
  if (number % prime == 0) {
    print('$number is divisible by $prime');
  }
}

Square Root Function (dart:math)

The sqrt() function from dart:math calculates the square root of a number. It’s useful for optimizing prime checking - you only need to check divisors up to the square root.

import 'dart:math';

void main() {
  int number = 17;
  
  // Calculate square root
  double sqrtValue = sqrt(number);
  print(sqrtValue); // 4.123105625617661
  
  // Convert to integer
  int sqrtInt = sqrt(number).toInt();
  print(sqrtInt); // 4
  
  // Use for optimization: only check up to sqrt
  for (int i = 2; i <= sqrtInt; i++) {
    if (number % i == 0) {
      print('Not prime');
      break;
    }
  }
}

Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

void main() {
  // Prime checking optimization:
  // 1. Only check up to sqrt(number)
  // 2. Only check against previously found primes
  // 3. Skip even numbers (except 2)
  
  bool isPrime(int n, List<int> primes) {
    int sqrtN = sqrt(n).toInt();
    for (int prime in primes) {
      if (prime > sqrtN) break;
      if (n % prime == 0) return false;
    }
    return true;
  }
}

Optimization Techniques

Several optimizations make prime finding more efficient:

Skip even numbers: After 2, all primes are odd
Check only up to sqrt(n): If n has a divisor > sqrt(n), it also has one < sqrt(n)
Check only against found primes: Only test divisibility by primes we’ve already found

void main() {
  List<int> primes = [2];
  int candidate = 3; // Start with 3 (first odd after 2)
  
  // Skip even numbers
  while (primes.length < 10) {
    if (isPrime(candidate, primes)) {
      primes.add(candidate);
    }
    candidate += 2; // Only check odd numbers
  }
}

Helper Methods

Helper methods (often private methods starting with _) encapsulate reusable logic, making code more organized and maintainable.

class NthPrime {
  // Public method
  int prime(int n) {
    // Uses helper method
    return _isPrimeOptimized(5, [2, 3]) ? 5 : 0;
  }
  
  // Private helper method
  bool _isPrimeOptimized(int number, List<int> primes) {
    // Prime checking logic
    return true;
  }
}

Conditional Logic

Conditional statements allow you to execute different code based on conditions. This is essential for handling edge cases and special values.

void main() {
  int findPrime(int n) {
    // Handle edge cases
    if (n < 1) {
      throw ArgumentError('Invalid input');
    }
    
    if (n == 1) {
      return 2; // First prime is 2
    }
    
    // Normal case
    // Find nth prime...
    return 0;
  }
}

Integer Conversion

The toInt() method converts a floating-point number to an integer, truncating any decimal part.

import 'dart:math';

void main() {
  double sqrtValue = sqrt(17); // 4.123...
  int sqrtInt = sqrtValue.toInt(); // 4
  
  // Use in loops
  for (int i = 2; i <= sqrt(17).toInt(); i++) {
    // Check divisors
  }
}

List.last Property

The last property returns the last element of a list. It’s useful for getting the most recently added prime.

void main() {
  List<int> primes = [2, 3, 5, 7, 11];
  
  // Get last element
  int lastPrime = primes.last;
  print(lastPrime); // 11
  
  // After adding more primes
  primes.add(13);
  print(primes.last); // 13
}

Introduction

Given a number n, determine what the nth prime is.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

If your language provides methods in the standard library to deal with prime numbers, pretend they don’t exist and implement them yourself.

What is a prime number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Prime numbers are fundamental in number theory and have applications in cryptography, computer science, and mathematics.

— Number Theory

How can we find the nth prime?

To find the nth prime:

Handle edge cases:
- Throw error if n < 1
- Return 2 immediately if n == 1 (first prime)
Initialize: Start with primes list containing [2], candidate = 3
Find primes: Loop until we have n primes:
- Check if candidate is prime using optimized method
- If prime, add to list
- Increment candidate by 2 (skip even numbers)
Return result: Return the last prime in the list

The key optimizations:

Skip even numbers: After 2, all primes are odd
Check only up to sqrt(n): If n has a divisor > sqrt(n), it also has one < sqrt(n)
Check only against found primes: Only test divisibility by primes we’ve already found

For example, to find the 6th prime:

Start: primes = [2], candidate = 3
3 is prime → primes = [2, 3], candidate = 5
5 is prime → primes = [2, 3, 5], candidate = 7
7 is prime → primes = [2, 3, 5, 7], candidate = 9
9 is not prime (divisible by 3) → candidate = 11
11 is prime → primes = [2, 3, 5, 7, 11], candidate = 13
13 is prime → primes = [2, 3, 5, 7, 11, 13] → length = 6
Return 13

Solution

import 'dart:math';

class NthPrime {
  int prime(int n) {
    if (n < 1) throw ArgumentError('There is no zeroth prime');

    if (n == 1) return 2;

    final primes = [2];
    int candidate = 3;

    while (primes.length < n) {
      if (_isPrimeOptimized(candidate, primes)) {
        primes.add(candidate);
      }
      candidate += 2;
    }

    return primes.last;
  }

  bool _isPrimeOptimized(int number, List<int> primes) {
    final sqrtNum = sqrt(number).toInt();
    for (final prime in primes) {
      if (prime > sqrtNum) break;
      if (number % prime == 0) return false;
    }
    return true;
  }
}

Let’s break down the solution:

import 'dart:math'; - Imports the math library:
- Provides the sqrt() function for calculating square roots
- Needed for optimization in prime checking
int prime(int n) - Main method that finds the nth prime:
- Takes n (the position of the prime we want)
- Returns the nth prime number
if (n < 1) throw ArgumentError(...) - Input validation:
- Checks if n is less than 1
- Throws an ArgumentError with a descriptive message
- Ensures only valid inputs are processed
if (n == 1) return 2; - Handle first prime:
- Returns 2 immediately (the first and only even prime)
- Avoids unnecessary computation for the simplest case
final primes = [2]; int candidate = 3; - Initialize:
- primes: List to store found primes, starting with 2
- candidate: Current number being tested, starts at 3 (first odd after 2)
while (primes.length < n) - Loop until we have n primes:
- Continues as long as we haven’t found enough primes
- Stops when primes.length equals n
if (_isPrimeOptimized(candidate, primes)) - Check if candidate is prime:
- Calls helper method to check if candidate is prime
- Only checks against previously found primes (optimization)
primes.add(candidate) - Add prime to list:
- If candidate is prime, add it to the primes list
candidate += 2 - Skip even numbers:
- Increments candidate by 2 (only checks odd numbers)
- After 2, all primes are odd, so this optimization is safe
return primes.last - Return the nth prime:
- Returns the last element in the primes list
- This is the nth prime we were looking for
bool _isPrimeOptimized(int number, List<int> primes) - Helper method for prime checking:
- Takes the number to check and list of known primes
- final sqrtNum = sqrt(number).toInt(): Calculates square root and converts to int
  - Only need to check divisors up to sqrt(number)
- for (final prime in primes): Iterates through known primes
- if (prime > sqrtNum) break: Early exit optimization
  - If we’ve checked all primes up to sqrt(number), number is prime
- if (number % prime == 0) return false: Check divisibility
  - If number is divisible by any prime, it’s not prime
- return true: If no divisors found, number is prime

The solution efficiently finds the nth prime using multiple optimizations: skipping even numbers, only checking up to the square root, and only testing against previously found primes. This makes it much faster than naive approaches.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel