Consecutive Primes challenge at CodeEval.com

Question

I am working through a new challenge on CodeEval.com and I think I am getting a correct result but I can't get through their grader. I am not exactly sure where error is. I didn't post this on stack overflow because I also would like to get your opinion on the code and the algorithm that I came up to solve this.

This is the assignment: Consecutive Primes Challenge

Alice has an even number of N beads, and each bead has a number from 1 to N painted on it. She would like to make a necklace out of all the beads, with a special requirement: any two beads next to each other on the necklace must sum to a prime number. Alice needs your help to calculate how many ways it is possible to do so.

For example:

N = 4

There are two possible ways to build the necklace. Note that the last bead connects to the first bead.

1 2 3 4
1 4 3 2

Note: The necklace should be unique. For example: 1 2 3 4 is the same as 2 3 4 1 and 3 4 1 2 and 4 1 2 3.

To solve if first tried recursion but that was running very slowly because of going through all the permutations. The inputs consists of one even integer on a line. Each integer N is 2 <= N <= 18.

First i tried to do it with recursion but that was taking way too long going through all the permutation. Then i tried to do is creating two arrays with odd and even numbers and going through them picking the number which will give me a prime when i add it to the last number picked and removing it from the array. The loop goes through all the numbers until it finds enough for a necklace or exits the loop.

    BOOL isPrime(int number){
        for(int i = 2;i<(int)(number/2)+1;i++){
            if (number%i == 0) {
                return false;
            }
        }
        return true;
    }

    BOOL isEven(int number)
    {
        if(number%2==0){
            return true;
        }
        return false;
    }


    NSMutableArray *  createEvenNumbersArray(int num)
    {
        NSMutableArray *evenNumArray = [[NSMutableArray alloc]initWithCapacity:num];
        for (int i=2; i<=num; i+=2) {
            [evenNumArray addObject:[NSNumber numberWithInt:i]];
        }
        return evenNumArray;
    }

    NSMutableArray * createOddNumbersArray(int num)
    {
        NSMutableArray *oddNumArray = [[NSMutableArray alloc]initWithCapacity:num];
        for (int i=3; i<=num; i+=2) {
            [oddNumArray addObject:[NSNumber numberWithInt:i]];
        }
        return oddNumArray;
    }



    int calculateConsecutive(int input)
    {
        int count = 0;
        BOOL evenFound = NO;
        BOOL oddFound = NO;
        NSMutableArray *oddNumArray = createOddNumbersArray(input); //creates odd number array with all the possiblities
        NSMutableArray *evenNumArray = createEvenNumbersArray(input); // create even number array with all the possibilities
        NSMutableArray *necklace = [[NSMutableArray alloc]init];
        [necklace addObject:[NSNumber numberWithInt:1]]; // start the necklace with 1 to get rid of duplicate necklaces
        for (int i = 2; i<=input; i+=2) { // goes through all the possibilities for the second bit to create the necklase
            NSMutableArray *tempOddNumArray = [oddNumArray mutableCopy]; // populate odd number array
            NSMutableArray *tempEvenNumArray = [evenNumArray mutableCopy]; // puplate even number array
            if(isPrime([[necklace lastObject] intValue] + i)){
                [tempEvenNumArray removeObject:[NSNumber numberWithInt:i]]; //remove number that we added to the necklase
                [necklace addObject:[NSNumber numberWithInt:i]];
                while ([necklace count]<=input) { // start creating the necklace after two numbers were added
                    oddFound = NO;
                    evenFound = NO;
                    for(NSNumber *oddNumber in tempOddNumArray){ // find the odd number possibility from the numbers that are left in the array
                        if(isPrime([[necklace lastObject] intValue] + oddNumber.intValue)){
                            [necklace addObject:oddNumber];
                            oddFound = YES;
                            break;
                        }
                    }
                    if (!oddFound) {
                        break;
                    }else{
                        [tempOddNumArray removeObject:[necklace lastObject]];
                    }
                    for(NSNumber *evenNumber in tempEvenNumArray){ // find the odd number possibility from the numbers that are left in the array
                        if(isPrime([[necklace lastObject] intValue] + evenNumber.intValue)){
                            [necklace addObject:evenNumber];
                            evenFound = YES;
                            break;
                        }
                    }
                    if (!evenFound) {
                        break;
                    }else{
                        [tempEvenNumArray removeObject:[necklace lastObject]];
                    }
                    if (([tempOddNumArray count] == 0) || ([tempEvenNumArray count] == 0) ){
                        break;
                    }

                }
            }
            if (([necklace count] == input) && (isPrime([[necklace lastObject] intValue]+[[necklace firstObject] intValue]))) {
                // check to make sure that the necklace is full and if the sum of the last number and first number is prime
                count= count + 1;
            }
            NSLog(@"%@",necklace);

            [necklace removeAllObjects];
            [necklace addObject:[NSNumber numberWithInt:1]];
        }
        return count;
    }

    -(void)primesMain
    {
        int necklaceCount = 0;
        int input = 18;
        if (isEven(input)) {
            necklaceCount = calculateConsecutive(input);
        }
        NSLog(@"%d",necklaceCount);
    }

-(void)viewDidLoad
{
     [self primesMain];
}

Here is the revised code with a solution as a new question.

Answer 1

Unfortunately, I've never handled objective-c code, but your algorithm is pretty convoluted and hard to analyse if you're missing any use-cases. It would be best for you and others if you could split some code fragments into smaller chuncks named appropriatelly.

Also, it might not be accepted as a solution because you don't return 0 if input is not even.

On the algorithm front - the most general solution to this kind of problem is backtracking. This way you don't miss solutions and the steps - incrementation and validation - are clearly visible in a brief inspection. Added benefit is that the code writes as a mirrot to the requirements for the problem. Other small optimizations to your code you could do:

    BOOL isPrime(int number){
        int max = (int)(number/2) + 1;//you skip calculating the division at each iteration
        for(int i = 2; i < max; i++){
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    BOOL isEven(int number)
    {
        return number%2 == 0;
    }

Not really applicable here, but there more efficient ways to calculate primality