Exercism - Prime Factors

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.

Lists

Lists are ordered collections of items. You can add elements dynamically as you find prime factors.

void main() {
  // Create empty list
  List<int> factors = <int>[];
  
  // Add elements
  factors.add(2);
  factors.add(3);
  factors.add(5);
  print(factors); // [2, 3, 5]
  
  // Add multiple times for repeated factors
  factors.add(2);
  print(factors); // [2, 3, 5, 2]
}

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() {
  int remaining = 60;
  
  // Continue until remaining is 1
  while (remaining > 1) {
    // Find and divide by factors
    remaining = remaining ~/ 2;
    print(remaining); // 30, 15, 7, 3, 1...
  }
}

Nested While Loops

Nested while loops allow you to have an inner loop that continues while a condition is true, within an outer loop that also continues while another condition is true.

void main() {
  int remaining = 60;
  int divisor = 2;
  
  // Outer loop: continue until remaining is 1
  while (remaining > 1) {
    // Inner loop: divide by same divisor multiple times
    while (remaining % divisor == 0) {
      remaining = remaining ~/ divisor;
      print('Divided by $divisor, remaining: $remaining');
    }
    divisor++; // Move to next divisor
  }
}

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 2
  print(15 % 2); // 1 (not divisible)
  print(15 % 3); // 0 (divisible)
  print(15 % 5); // 0 (divisible)
  
  // Use in loop condition
  while (number % 3 == 0) {
    print('Divisible by 3');
    number = number ~/ 3;
  }
}

Integer Division Assignment

The integer division assignment operator (~/=) divides a variable by a value and assigns the result back to the variable. It’s equivalent to variable = variable ~/ value.

void main() {
  int remaining = 60;
  
  // Integer division assignment
  remaining ~/= 2;
  print(remaining); // 30
  
  // Equivalent to:
  remaining = remaining ~/ 2;
  print(remaining); // 15
  
  // Use in loops
  while (remaining % 2 == 0) {
    remaining ~/= 2; // Divide and update
    print(remaining);
  }
}

Increment Operator

The increment operator (++) increases a variable by 1. It’s used to move to the next potential divisor.

void main() {
  int divisor = 2;
  
  // Increment
  divisor++;
  print(divisor); // 3
  
  // Use in loops
  while (divisor < 10) {
    print(divisor);
    divisor++; // Move to next number
  }
  // Output: 2, 3, 4, 5, 6, 7, 8, 9
}

Conditional Logic

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

void main() {
  int number = 0;
  
  // Handle edge cases
  if (number <= 1) {
    return []; // No prime factors for 0 or 1
  }
  
  // Normal processing
  // Find factors...
}

Comparison Operators

Comparison operators (>, <=, ==) compare values and return boolean results. They’re used in loop conditions and if statements.

void main() {
  int remaining = 5;
  
  // Check if greater than
  print(remaining > 1); // true
  
  // Check if less than or equal
  print(remaining <= 1); // false
  
  // Use in loop condition
  while (remaining > 1) {
    // Process...
  }
}

Introduction

Compute the prime factors of a given natural number.

A prime number is only evenly divisible by itself and 1.

Note that 1 is not a prime number.

Example

What are the prime factors of 60?

Our first divisor is 2. 2 goes into 60, leaving 30.

2 goes into 30, leaving 15.

2 doesn’t go cleanly into 15. So let’s move on to our next divisor, 3.

3 goes cleanly into 15, leaving 5.

3 does not go cleanly into 5. The next possible factor is 4.

4 does not go cleanly into 5. The next possible factor is 5.

5 does go cleanly into 5.

We’re left only with 1, so now, we’re done.

Our successful divisors in that computation represent the list of prime factors of 60: 2, 2, 3, and 5.

You can check this yourself:

2 × 2 × 3 × 5 = 4 × 15 = 60

Success!

What are prime factors?

Prime factors are the prime numbers that multiply together to give a particular number. For example, the prime factors of 60 are 2, 2, 3, and 5, because 2 × 2 × 3 × 5 = 60. Every natural number greater than 1 can be expressed as a unique product of prime factors (this is known as the fundamental theorem of arithmetic).

— Number Theory

How can we find prime factors?

To find prime factors:

1. Handle edge cases: Return empty list for numbers ≤ 1
2. Start with divisor 2: The smallest prime number
3. Divide repeatedly: While the number is divisible by the current divisor, divide it and add the divisor to the result
4. Move to next divisor: Increment the divisor and repeat
5. Continue until done: Stop when the remaining number is 1

The key insight is using nested while loops: the outer loop continues until we’ve factored everything, and the inner loop divides by the same divisor multiple times (to handle repeated factors like 2 × 2).

For example, with number 60:

• Divisor 2: 60 % 2 == 0 → divide: 30, add 2
• Divisor 2: 30 % 2 == 0 → divide: 15, add 2
• Divisor 2: 15 % 2 != 0 → move to next
• Divisor 3: 15 % 3 == 0 → divide: 5, add 3
• Divisor 3: 5 % 3 != 0 → move to next
• Divisor 4: 5 % 4 != 0 → move to next
• Divisor 5: 5 % 5 == 0 → divide: 1, add 5
• Remaining = 1 → done
• Result: [2, 2, 3, 5]

Solution

class PrimeFactors {
  List<int> factors(int number) {
    if (number <= 1) {
      return [];
    }
    
    final result = <int>[];
    var remaining = number;
    var divisor = 2;
    
    while (remaining > 1) {
      while (remaining % divisor == 0) {
        result.add(divisor);
        remaining ~/= divisor;
      }
      divisor++;
    }
    
    return result;
  }
}

Let’s break down the solution:

1. List<int> factors(int number) - Main method that finds prime factors:

   • Takes a natural number as input
   • Returns a list of prime factors

2. if (number <= 1) return [] - Handle edge cases:

   • Numbers ≤ 1 have no prime factors
   • Returns empty list immediately

3. final result = <int>[] - Initialize result list:

   • Will store all prime factors found
   • Uses type inference with <int>[] syntax

4. var remaining = number - Track remaining number:

   • Starts with the original number
   • Will be divided by factors until it becomes 1

5. var divisor = 2 - Start with smallest prime:

   • Begins with 2 (the smallest prime number)
   • Will increment to test larger divisors

6. while (remaining > 1) - Outer loop:

   • Continues until we’ve factored everything (remaining becomes 1)
   • Tests each divisor in sequence

7. while (remaining % divisor == 0) - Inner loop:

   • Continues while the remaining number is divisible by the current divisor
   • remaining % divisor == 0: Checks if divisible (remainder is 0)
   • result.add(divisor): Adds the divisor to the result list
   • remaining ~/= divisor: Divides remaining by divisor and updates it
   • This inner loop handles repeated factors (e.g., 2 × 2)

8. divisor++ - Move to next divisor:

   • Increments divisor to test the next number
   • Only reached when current divisor no longer divides evenly

9. return result - Return the prime factors:

   • Returns the list of all prime factors found

The solution efficiently finds prime factors by testing divisors in order, dividing out each factor completely before moving to the next. The nested while loops ensure we capture all occurrences of each prime factor.

---

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