Truncatable primes | Project Euler | Problem #37
URL to the problem page: https://projecteuler.net/problem=37
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 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.
#include <iostream>
using namespace std;
int power(int a, int b) {
int result = 1;
for (int i = 0; i < b; i++) {
result = result * a;
}
return result;
}
int finddigits(int a) {
int cnt = 1;
while (a >= 10) {
a /= 10;
cnt++;
}
return cnt;
}
int main()
{
int i, j, a, b, n, digitnumber, cnt, cnt2 = 0, cnt3, cnt4, cnt5, cnt6, result = 0;
for (i = 22; cnt2 < 11; i++) {
cnt = 0;
cnt4 = 0;
cnt5 = 0;
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
cnt++;
break;
}
}
if (cnt != 0) {
continue;
}
digitnumber = finddigits(i);
int* digits = new int[digitnumber];
for (j = digitnumber; j > 0; j--) {
digits[j - 1] = (i % power(10, j)) / (power(10, (j - 1)));
}
if (digits[0] == 1 || digits[digitnumber - 1] == 1) {
continue;
}
int* numbers = new int[digitnumber - 1];
for (a = 0; a < (digitnumber - 1); a++) {
numbers[a] = 0;
}
for (b = digitnumber - 1, j = 0; b > 0, j < (digitnumber - 1); b--, j++) {
cnt3 = 0;
for (a = 0; a < b; a++) {
numbers[j] += (digits[a] * power(10, a));
}
for (a = 2; a <= sqrt(numbers[j]); a++) {
if (numbers[j] % a == 0) {
cnt3++;
break;
}
}
if (cnt3 != 0) {
cnt4++;
break;
}
}
if (cnt4 != 0) {
continue;
}
int* numbers2 = new int[digitnumber - 1];
for (a = 0; a < (digitnumber - 1); a++) {
numbers2[a] = 0;
}
for (a = 0, j = 0; a < (digitnumber - 1), j < (digitnumber - 1); a++, j++) {
cnt6 = 0;
for (b = a + 1, n = 0; b < digitnumber; b++, n++) {
numbers2[j] += digits[b] * (power(10, n));
}
for (b = 2; b <= sqrt(numbers2[j]); b++) {
if (numbers2[j] % b == 0) {
cnt6++;
break;
}
}
if (cnt6 != 0) {
cnt5++;
break;
}
}
if (cnt5 != 0) {
continue;
}
result += i;
cnt2++;
}
cout << endl << "Sum of the only eleven primes that are both truncatable from left to right and right to left is = " << result << endl;
return 0;
}
Comments
Post a Comment