Project Euler number 37

Question

Here's the problem statement:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

My code gives me a partial output. Only 5 or 6 of the eleven required primes are being outputted, 3797 not being one of them. So to find the error, I manually (on a piece of paper) ran the code for 3797 and somehow can't manage to find the glitch.

I think the error is in the second part, the part of code which checks whether the number is truncatable from the left.

Code:

#include<stdio.h>
      int isprime(int n) //Checks whether the number is prime or not
      {
        int i;
        if(n==1)
        return(0);
        for(i=2;i<n/2+1;i++)
        {

            if(n%i==0)
            {
                return(0);
                break;
            }   
        }
        return(1);      
      }
      int main(void)
      {
        int count=0,z=0;
        int i;
        int n;
        int x=1;
        int reverse2=0;
        int z1=0;
        int p;
        int count1=0;
        int digit;
        int k=1000000;
        int reverse=0;
        for(i=2;i<k;i++)
        {
            if(isprime(i)==1)
            {
                n=i;
                p=i;
                while(n>0) // This function removes the digits of the prime number from the right
                {
                    n=n/10;
                    if(isprime(n)==1)
                    {
                        count++;
                    }   
                    z++;
                }

                if(z==count) 
                {   
                        while(p>0) //Checks whether number is left truncatable 
                        {   
                            digit=p%10;
                            p=p/10;
                                if(z1==0)
                                {
                                    reverse=digit;//here reverse doesn't refer to reversing the number. It builds the number one digit at a time from right to left.
                                }
                                else
                                {   
                                    reverse=digit*x*10+reverse;
                                    x++;
                                }
                                if(isprime(reverse)==1)
                                {
                                    count1++;
                                }
                            z1++;

                        }

                        if(z1==count1)
                        printf("%d ",i);

                }
                    z=0;
                    z1=0;
                    count1=0;
                    count=0;
                    reverse=0;
                    reverse2=0;
                    x=1;
            }                                                                                                                                                                                       
        }   

      }

Answer 1

Your left truncatable check is wrong. I did it differently, simpler.

#include<stdio.h>
int isprime(int n) //Checks whether the number is prime or not
{
    int i;
    if(n==1)
        return(0);
    for(i=2;i<n/2+1;i++)
    {

        if(n%i==0)
        {
            return(0);
            break;
        }   
    }
    return(1);      
}
int power(int a, int b){
    int r = 1;
    int i=0;
    for (i=0;i<b;i++){
        r = r * a;
    }
    return r;
}

int main(void)
{
    int count=0,z=0;
    int i;
    int n;
    int z1=0;
    int p;
    int count1=0;
    int digits;
    int k=1000000;
    for(i=2;i<k;i++)
    {
        if(isprime(i)==1)
        {
            z = 0;
            count = 0;
            n=i;
            p=i;
            while(n>0) // This function removes the digits of the prime number from the right
            {
                n=n/10;
                if(isprime(n)==1)
                {
                    count++;
                }else{
                    count = -1;
                    break;
                }   
                z++;
            }

            if(z==count) 
            {   
                z1= 0;
                count1=0;
                n = i;
                p= i;
                while(p>0) //Checks whether number is left truncatable 
                {   
                    digits=n%power(10,z1+1);
                    p = p /10;
                    if (isprime(digits)==1)
                    {
                        count1++; 
                    }else{
                        count1 =-1;
                        break;
                    }
                    z1++;
                }

                if(z1==count1)
                    printf("%d\n ",i);

            }
        }                                                                                                                                                                                       
    }   

}