【入门】纯粹素数,c++c++太难

Question

描述

纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。求出所有小于3000的四位的纯粹素数。

输入描述

无

输出描述

按从小到大的顺序输出若干个纯粹素数，每行一个。

用例输入 1

用例输出 1

来源

函数问题

Answer 1

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7679207
• 这篇博客也不错, 你可以看下蓝桥杯真题 迷宫 c++代码实现 下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、
• 您还可以看一下 朱有鹏老师的朱老师C++课程第3部分3.4.模板特化与类型萃取课程中的 3.4.1.从案例中理解什么是模板特化1小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【基础算法】关于高精度计算的问题【很高位数数据的加减乘除(相关代码用C++实现)】中的 1.高精度加法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  • 高精度加法是两个位数很大的两个数相加，例如1234567898756432123456789 + 66666666666666666666666，这时候我们用平常的整型或者长整型去存放数据都是会溢出导致数据丢失的，所以此时我们可以用一个数组来存放每个数相对应位上的数（使用vector<int>， 假设这两个高精度数都大于0）。

  • 不过在C++中，直接将数输入到vector中是不可取的，并且加法是从两个数的低位开始相加一直加到高位，如果我们正常输入从高位开始存放的话，对于后面程序的设计是不方便的，所以这里我们用string来表示相应高精度数，然后将这个string从低位开始转化成整数依次存放在vector<int>当中，这样两个vector<int>就是我们想要的高精度数了。

  • 同时我们需要另一个vector<int>来存放相加后的数，由于相加数的存放是倒着的，所以最终的结果也是倒着存放在vector<int>中的，此时打印就需要从后面往前面打印输出。

  • 加法不难，但要注意的是，如何在程序中表示进位，我们都知道，每一位数相加超过10就要进位1，表示这一位的前一位要+1。3和5相加为8不用进位，而7和8相加要进位，最后在这一位留下来的是（7 + 8）- 10 = 5，在程序中可以表示为（7 + 8）% 10。而这个%10就显得格外重要了，如果你相加后的数小于10，它%10后，还是它本身，如果大于10，它就相当于去掉一个10，剩下的数就放进表示最终答案的vector<int>。

  • 最后要注意的是，两个位上的数相加后的结果要/=10,这是表示要除去这一位该留下的结果以及得到需要进的位，例如：7 + 8 = 15 ，在该位应该留下的最终结果为 15 % 10 = 5，最后 15 /= 10 得到1，表示要进位1，该位的结果5除去。

  下面是相关操作的代码实现：

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  vector<int> add(vector<int>& A, vector<int>& B)
  {
  	vector<int> C;
  
  	int tmp = 0;
  
  	for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
  	{
  		if (i < A.size()) tmp += A[i];
  		if (i < B.size()) tmp += B[i];
  		C.push_back(tmp % 10);
  		tmp /= 10;
  	}
  
  	while (C.size() > 1 && C.back() == 0) C.pop_back();
  
  	return C;
  }
  
  int main()
  {
  	string a, b;
  	cin >> a >> b;
  	vector<int> A, B;
  
  	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  	auto C = add(A, B);
  
  	for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  	cout << endl;
  
  	return 0;
  }
  

  代码测试：

  

  

  代码细节解释：

  • 这里是将高精度数分别从低位到高位存放到两个vector<int>中；

  	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  

  • 这个for循环便是相加的代码，两个if表示如果这个数的位数加完了，就停止加入tmp，判断条件表示将tmp加完为止（也就是如果两个数位数相同，最高位相加完后又进了一位，此时 tmp 为 1 并且不在加入数据，这个1 也是有效位，因此需要加入C中）

  	for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
  	{
  		if (i < A.size()) tmp += A[i];
  		if (i < B.size()) tmp += B[i];
  		C.push_back(tmp % 10);
  		tmp /= 10;
  	}
  

  • 这个while表示去掉前导0，虽然加法不会出现前导0的情况，但不排除输入的数据都为0的情况。

  	while (C.size() > 1 && C.back() == 0) C.pop_back();
  

  ---

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^