Expected complexity is a bit worse than logarithmic, but much better than linear. Linear solution will not pass, but it's very easy to come up with much more performant solution than linear.

Do not focus on the loop step, step of 2 is perfectly OK, but step of 1 would also pass the kata. More improtant is the upper bound of your loop. Try to figure out how far you need to loop, and at what point you are perfectly sure that you do not need to loop any further.

Good thing is that your solution is rather correct, because it returns correct answers.

Bad thing is that it's too slow, and manages to pass ~35 random tests out of 1000. You need to think how to improve performance, but it might be easier than you think. This kata does not require memoization, and your solution will pass even if it performs separate calculations for every input. You just need to figure out how high your loop should go before being certain that the number is (or is not) prime.