Unprimeable numbers | Rosetta Code | #16
URL to the problem page: http://rosettacode.org/wiki/Unprimeable_numbers
As used here, all unprimeable numbers (positive integers) are always expressed in base ten.
Unprimeable numbers are composite numbers that always remain composite when a single decimal digit of the number is changed.
(arithmetic) that cannot be turned into a prime number by changing just one of its digits to any other digit.
Unprimeable numbers are also spelled: unprimable.
All one─ and two─digit numbers can be turned into primes by changing a single decimal digit.
Examples:
190 isn't unprimeable, because by changing the zero digit into a three yields 193, which is a prime.
The number 200 is unprimeable, since none of the numbers 201, 202, 203, ··· 209 are prime, and all the other numbers obtained by changing a single digit to produce 100, 300, 400, ··· 900, or 210, 220, 230, ··· 290 which are all even.
It is valid to change 189 into 089 by changing the 1 (one) into a 0 (zero), which then the leading zero can be removed, and then treated as if the "new" number is 89.
Show the first 35 unprimeable numbers.
Show the 600th unprimeable number.
As used here, all unprimeable numbers (positive integers) are always expressed in base ten.
Unprimeable numbers are composite numbers that always remain composite when a single decimal digit of the number is changed.
(arithmetic) that cannot be turned into a prime number by changing just one of its digits to any other digit.
Unprimeable numbers are also spelled: unprimable.
All one─ and two─digit numbers can be turned into primes by changing a single decimal digit.
Examples:
190 isn't unprimeable, because by changing the zero digit into a three yields 193, which is a prime.
The number 200 is unprimeable, since none of the numbers 201, 202, 203, ··· 209 are prime, and all the other numbers obtained by changing a single digit to produce 100, 300, 400, ··· 900, or 210, 220, 230, ··· 290 which are all even.
It is valid to change 189 into 089 by changing the 1 (one) into a 0 (zero), which then the leading zero can be removed, and then treated as if the "new" number is 89.
Show the first 35 unprimeable numbers.
Show the 600th unprimeable number.
#include <iostream>
using namespace std;
bool primecheck(int a) {
int cnt = 0;
for (int i = 2; i <= sqrt(a); i++) {
if (a % i == 0) {
cnt++;
break;
}
}
if (cnt == 0) {
return 1;
}
else {
return 0;
}
}
int power(int a, int b) {
int result = 1;
for (int i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main() {
int tmp, tmp2, cnt = 0, cnt2, digits, sum;
cout << "First 35 unprimeable numbers are:" << endl;
for (int i = 1; cnt < 600; i++) {
if (primecheck(i) == 1) {
continue;
}
digits = 1;
tmp = i;
while (tmp >= 10) {
digits++;
tmp /= 10;
}
int* numbers = new int[digits];
for (int j = 0; j < digits; j++) {
numbers[j] = (i % power(10, j + 1)) / power(10, j);
}
for (int m = 0; m < digits; m++) {
tmp2 = numbers[m];
for (int j = 0; j < 10; j++) {
if (numbers[m] == j) {
continue;
}
numbers[m] = j;
cnt2 = 0;
sum = 0;
for (int k = 0; k < digits; k++) {
sum += (numbers[k] * power(10, k));
}
if (primecheck(sum) == 1 && sum != 0) {
cnt2++;
break;
}
}
if (cnt2 != 0) {
break;
}
numbers[m] = tmp2;
}
if (cnt2 == 0) {
if (cnt < 35) {
cout << i << ", ";
}
else if (cnt == 599) {
cout << endl << endl << "600th unprimeable number is = " << i << endl;
}
cnt++;
}
}
return 0;
}
Comments
Post a Comment