As title the problem is to workout how many prime numbers can be written in all rotations and still be prime.
Ie 193939, 939391, 393919, 939193, 391939, 919393 are all prime numbers. Here is my effort
Code:
#include <stdio.h>
#include <stdlib.h>
#define Limit 1000000
int IsPrime( char *, int );
int NumRotate( char *, int );
int main()
{
unsigned long Counter = 1;
char NumSieve[Limit] = { 0 };
for( int i = 4; i < Limit; i += 2 )
{
NumSieve[ i - 1 ] = 1;
}
for ( int i = 3; i < 1000; i += 2 ) //only test odd numbers
{
if ( NumSieve[ i - 1 ] == 0 )
{
for ( int j = 2 * i; j < Limit; j += i )
{
NumSieve[ j - 1 ] = 1;
}
}
}
for ( int i = 3; i < Limit; i++ )
{
if ( NumSieve[ i - 1 ] == 0 )
{
if ( NumRotate( NumSieve, i ) == 1)
{
Counter++;
}
}
}
printf("number of rotatable primes between 1 and %d is %lu\n", Limit, Counter);
return 0;
}
int IsPrime( char *PNums, int x )
{
return PNums[ x - 1 ] == 0 ? 1 : -1;
}
int NumRotate( char *PNums, int x )
{
if ( x % 10 == x) //single digit number so no need to test
{
return 1;
}
else if ( x % 100 == x ) // 2 digit number
{
int SecondDigit = x % 10, FirstDigit = ( x - SecondDigit ) / 10;
if ( IsPrime( PNums, SecondDigit * 10 + FirstDigit ) == -1 )
{
return -1;
}
}
else if ( x % 1000 == x ) //3 digits
{
int FirstDigit = ( x - x % 100 ) / 100, ThirdDigit = x % 10;
int SecondDigit = ( x - ( FirstDigit * 100 + ThirdDigit ) ) / 10, loop = 2;
do
{
int tmp = FirstDigit;
FirstDigit = SecondDigit;
SecondDigit = ThirdDigit;
ThirdDigit = tmp;
if ( FirstDigit == 0 )
return -1;
if ( IsPrime( PNums, ( FirstDigit * 100 ) + ( SecondDigit * 10 ) + ThirdDigit ) == -1 )
{
return -1;
}
--loop;
} while ( loop > 0 );
}
else if ( x % 10000 == x ) //4 digits
{
int FirstDigit = ( x - x % 1000) / 1000, FourthDigit = x % 10, Loop = 3;
int ThirdDigit = ( x % 100 - FourthDigit ) / 10, SecondDigit = (( x - x % 100) / 100 ) % 10;
do
{
int tmpNum = FirstDigit;
FirstDigit = SecondDigit;
SecondDigit = ThirdDigit;
ThirdDigit = FourthDigit;
FourthDigit = tmpNum;
if ( FirstDigit == 0 )
return -1;
if ( IsPrime( PNums, ( FirstDigit * 1000) + ( SecondDigit * 100 ) + ( ThirdDigit * 10 ) + FourthDigit ) == -1 )
return -1;
--Loop;
} while ( Loop > 0 );
}
else if ( x % 100000 == x ) // 5 digits
{
int FirstDigit = ( x - x % 10000) / 10000, FithDigit = x % 10, FourthDigit = ( x % 100 - FithDigit ) / 10, Loop = 4;
int ThirdDigit = ( x % 1000 - ( FourthDigit * 10 + FithDigit ) ) / 100;
int SecondDigit = ( x % 10000 - ( ThirdDigit * 100 + FourthDigit * 10 + FithDigit ) ) / 1000;
do
{
int TmpNum = FirstDigit;
FirstDigit = SecondDigit;
SecondDigit = ThirdDigit;
ThirdDigit = FourthDigit;
FourthDigit = FithDigit;
FithDigit = TmpNum;
if ( FirstDigit == 0 )
return -1;
if ( IsPrime( PNums, ( FirstDigit * 10000) + ( SecondDigit * 1000 ) + ( ThirdDigit * 100 ) + ( FourthDigit * 10 ) + FithDigit ) == -1 )
return -1;
--Loop;
} while (Loop > 0 );
}
else if ( x % 1000000 ) // 6 digits
{
int FirstDigit = ( x - x % 100000 ) / 100000, SixthDigit = x % 10, FithDigit = ( x % 100 - SixthDigit ) / 10, Loop = 5;
int FourthDigit = ( x % 1000 - ( FithDigit * 10 ) + SixthDigit ) / 100;
int ThirdDigit = ( x % 10000 - ( FourthDigit * 100 ) + ( FithDigit * 10 ) + SixthDigit ) /1000;
int SecondDigit = ( x % 100000 - ( ThirdDigit * 1000) + ( FourthDigit * 100 ) + ( FithDigit * 10 ) + SixthDigit ) / 10000;
do
{
int TmpNum = FirstDigit;
FirstDigit = SecondDigit;
SecondDigit = ThirdDigit;
ThirdDigit = FourthDigit;
FourthDigit = FithDigit;
FithDigit = SixthDigit;
SixthDigit = TmpNum;
if ( FirstDigit == 0 )
return -1;
if ( IsPrime( PNums, ( FirstDigit * 100000) + ( SecondDigit * 10000 ) + ( ThirdDigit * 1000 ) + ( FourthDigit * 100 ) + ( FithDigit * 10 ) + SixthDigit ) == -1 )
return -1;
--Loop;
} while (Loop > 0 );
}
return 1;
}
It works and i get the correct answer but the rotate function is awkward