将一个长度小于10位的数字串拆成2段,使其和为最小的素数。
例如数字串‘13304’
拆的方法有:
1 + 3304 = 3305
13 + 304 = 317
133 + 04 = 137
1330 + 4 = 1334
从上面可看出,和为素数的有:317 与137,最小的是137
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
// 素数判断
bool isPrime(int number)
{
for (int i = 2; i <= sqrt(number); ++i)
if (number % i == 0)
return false;
return true;
}
int main()
{
string number;
cin >> number;
int min = INT_MAX; //记录最小和的素数
int a, b = 0;//记录拆开的两数
for (int i = 0; i < number.length() - 1; ++i)
{
string A = number.substr(0, i + 1);
string B = number.substr(i + 1, number.length() - 1 - i);
a = atoi(A.c_str());
b = atoi(B.c_str());
if (isPrime(a + b))
if (a + b < min)
min = a + b;
}
cout << min << endl;
return 0;
}
思路就是简单的遍历,找出和最小且为素数的组合,如需代码实现可私聊
a = atoi(A.c_str());
这个报错了