50-prime-ant-performance-version.md

Problem:

Preface

This is the performance version of the Prime Ant kata. If you did not complete it yet, you should begin there.

Description

The "prime ant" is an obstinate animal that navigates the integers and divides them until there are only primes left!

Initially, we have an infinite array A containing all the integers >= 2 : [2, 3, 4, 5, 6, ... ]

Let p be the position of the ant on the array. Initially, p = 0 (the array is 0-indexed)

Each turn, the ant will move as follows:

• if A[p] is prime, the ant moves to the next position : p += 1
• else, if A[p] is a composite number, let q be its smallest divisor > 1. We divide A[p] by q, and we add q to A[p-1]. The ant moves to the previous position: p -= 1

Here are the first moves for the ant:

2  3  4  5  6  7  8  9  ...    # 2 is prime: go on
^
2  3  4  5  6  7  8  9  ...    # 3 is prime: go on
   ^
2  3  4  5  6  7  8  9  ...    # 4 is composite: go back and update
      ^
2  5  2  5  6  7  8  9  ...    # 5 is prime: go on
   ^
2  5  2  5  6  7  8  9  ...    # 2 is prime: go on
      ^
2  5  2  5  6  7  8  9  ...    # 5 is prime: go on
         ^
etc.

Your task

Your function should return the list of integers up to (and including) the ant's position after n moves (that is A[0:p+1])

Examples

0        => [2]                                        # list size = 1
10       => [2, 5, 2, 7, 3, 7, 8]                      # size = 7
100      => [2, 5, 5, 5, 3, 3, 2, 3, 5, 3, 3, 5, 2, 7, 2, 13, 6]  # size = 17
1000     => [..., 5, 5, 2, 5, 3, 2, 7, 5, 3, 3]        # size = 83
10000    => [..., 7, 2, 7, 2, 5, 2, 3, 5, 5, 72]       # size = 513
100000   => [..., 2, 2, 7, 5, 3, 7, 7, 3, 5, 932]      # size = 3675
1000000  => [..., 2, 3, 5, 2, 5, 5, 7, 13, 113, 7161]  # size = 28643
10000000 => [..., 2, 2, 2, 7, 2, 3, 2, 7, 2, 4]        # size = 233369

Tests

As this is a performance kata, the tests start where the other kata stopped: 10000 < n < 1000000.

There are 200 random tests in the 10⁴ - 10⁵ range, and another 20 tests in the 10⁵ - 10⁶ range.

Epilogoue

If you're up to the challenge, try the advanced version of this kata: Prime Ant - Crazy Version

---

My other katas

If you enjoyed this kata then please try my other katas! :-)

Translations are welcome!

Solution