Truncatable primes - 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.
The following is my effort to sole this. the answer i get is 573 which makes sense until you consider there is only supposed to be 11 and the example given is bigger than the 11 i found
Code:
#include <stdio.h>
#include <stdlib.h>
#define Countto 1000000
int FindMod( int *, int );
void LoadPrimes( int *Primes );
int CheckPrime( int *, int );
int Truncatable( int *, int, int, int );
int main()
{
int NumSieve[Countto] = { 0 };
int Sum = 0, Counter = 0;
LoadPrimes( NumSieve );
for (int i = 11; i < Countto; i += 2)
{
int Mod = 10, Limit = FindMod( &Mod, i );
if ( CheckPrime( NumSieve, i % Mod) )
if ( Truncatable(NumSieve, Mod, Limit, i ) )
{
printf("%d\n", i);
Sum += i;
Counter++;
}
if ( Counter == 11 )
break;
}
printf("Sum of the 11 truncatable primes is: %d\n", Sum);
return 0;
}
int FindMod( int *Mod, int Num )
{
int Counter = 0;
while ( Num % *Mod < Num )
{
*Mod *= 10;
Counter++;
}
return Counter;
}
void LoadPrimes( int *Primes )
{
for ( int i = 4; i < Countto; i += 2 )
Primes[i] = 1;
for ( int i = 3; i < 1000; i += 2 )
{
if ( Primes[i] == 0 )
for ( int j = i * 2; j < Countto; j += i)
Primes[j] = 1;
}
}
int CheckPrime( int *Primes, int Index )
{
return Primes[Index] == 0; //Index is prime
}
int Truncatable( int *NumSieve, int Mod, int Limit, int i )
{
int TruncNum[Limit];
for ( int j = 0; j < Limit; j++ )
{
Mod /= 10;
if ( !CheckPrime( NumSieve, i % Mod ) )
return 0;
TruncNum[j] = i % Mod;
}
for ( int j = Limit - 1; j >= 0; j-- )
{
if ( !CheckPrime( NumSieve, ( i - TruncNum[j] ) / Mod ) )
return 0;
Mod *= 10;
}
return 1;
}
where am i going wrong