C++程序从给定数字打印最大可能的素数

给定一个整数，任务是找到可以从它中找到的最大素数。如果我们将整数视为数字字符串，则素数可以是任意长度的子字符串。下面给出的示例将说明问题的思路。

示例：

输入： 12691

输出： 691

说明： 数字12691中有三个数字是269,691。较大的数字是691，因此我们打印出来。

方法:

创建给定数字的字符串
计算该字符串的所有子串
检查哪些子串是素数
如果一个子串是素数，则通过与其他素数子串进行比较来最大化其值
返回素数子串的最大值

// C++程序：从给定数字打印最大
// 可能的素数
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
//检查子串是否为素数的函数
bool isprime(string f)
{
    int n = stoi(f);
   
    //检查特殊情况
    if (n <= 1)
        return false;
 
    //从2到n-1检查
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
int longp(int a)
{
    //将数字转换为字符串
    string d = to_string(a);
    int n = d.length();
    int c = INT_MIN;
    for (int i = 0; i < n; i++) {
        for (int len = 1; len <= n - i; len++) {
           
            //计算字符串的子串
            string p = d.substr(i, len);
           
            //将子字符串传递给素数检查函数
            if (isprime(p)) {
                int l = stoi(p);
               
                //存储素数子串的最大值
                c = max(c, l);
            }
        }
    }
    return c;
}
//主函数
int main()
{
 
    long long int n = 12691;
    int k = longp(n);
    cout << k;
    return 0;
}

输出

时间复杂度: O(N 3 )

辅助空间: O(1)