The difficulty is in that you need to write a regex, not a function.

A few hints:

• sieve of Erosthenes is solid and fast way to generate primes; however, a lot depends on the implementation. I suggest to write your version and time it to generate primes up to 10^6, and try to improve it. You can use an online IDE, e.g. https://repl.it ; further hints: half sieve, "rwh primes"
• test small code snippets on http://www.pythontutor.com -- the less steps it requires, the faster it will be
• do more easy katas, e.g. about digits sum: there are much quicker ways to get the digit sum of a number
• don't repeat yourself (DRY): reuse your existing code -- don't write a validity chacker for each method, just call the existing one
• etc

Always state the language in which you found the problem.
Fixed for Python.

should be, but the only way to pass the tests is to implement an iterative algorithm, this kata should not be 6kyu

it's not a variable, it's a function you have to call ;) (look at the example tests)

Are we only allowed solution sets with 2 or more dice?

Yes, as stated here:

The task for this kata is to get the amount of equivalent dice sets, having 2 dice at least,for a given set.

'))))' should equal '))((' means your function returned '))))' when it should return '))(('. The first one isn't the input value, print it to see what it is.