PTA-C++ 寻找最大素数

 本人只能想到比较笨的算法：通过循环嵌套循环的方法依次去判断组合出来的数是不是素数；比如1234567；从最高位数1开始，组合出1，12，123，1234，12345....然后后退一位，组合出：2，23，234，2345.....这样进行下去，在每次组合后判断是否是素数。先把所有的素数都找到后再来寻找出最大值。

代码如下：

#include
#include
#include
#include
int zhaosushu(int a)//判断是不是素数
{if (a == 0)return 0;if (a == 1)return 0;if (a == 2)return 1;else{if (a % 2 == 0)return 0;else{for (int i = 3;i <=sqrt(a);i+=2){if (a % i == 0){return 0;}}return 1;}
}}
using namespace std;
int main()
{string s1;int changdu = 0, max = 0, length = 0, temp;vectora;vectora1;cin >> s1;for (int i = 0;i < s1.size();i++)//把字符串各数字存入到数组中{a.push_back(s1[i] - '0');changdu++;}for (int i = 0;i < changdu; i++)//控制起始位置{temp = 0;for (int j = 0;j < changdu - i; j++)//从起始位置一直累次往后推{temp = temp * 10 + a[i + j];if (zhaosushu(temp))//把素数存起来{a1.push_back(temp);length++;}}}if (length == 0)//判断是否有素数{cout << "None";}else{for (int i = 0;i < length;i++)//找最大素数{if (a1[i] > max){max = a1[i];}}cout << max;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！