C++用递归方式输出100以内的质数

要求用递归方式求100以内的质数,并且打印出来,每5个一行

3个回答

int count = 0;
        for (int n = 2; n <= 100; n++)
        {
            int m = sqrt((float)n);
            for (int i = 2; i <= m; i++)
            {
                if (n % i == 0)
                    break;
                if (n > m){
                    if (count == 6){
                        cout << "\n";
                        count = 0;
                    }
                    else
                        cout << n << " ";
                    count ++;
                }
            }
        }
        system("pause");

#include
using namespace std;
bool isPrime(int i){
for(int j=2;j<=i/2;j++){
if (i%j == 0){
return false;
}
}
return true;
}
int main(void){

for(int i=2;i<100;i++){
    if(isPrime(i)){
        cout<<i<<endl;
    }
}

return 0;

}

简单的求质数方式,就是将当前要确认的数,比如87,和87前面已经确认了的质数进行整除,如果有一个能除尽,则表示是合数,如果都除完了还没有整除,则找到一个新的质数。

所以,第一个是需要数据记录已经找到的质数。使用vector可以存储。
第二个,用当前的数去除,得到结果。那么结果有两种,一种是除尽了,不是质数,一种是遍历完vector之后,还是没有除尽,则需要加入到vector中。
第三个,既然是递归,则要设计出一个递归的函数出来。递归函数就是类似:
   /——  退出   x=1
f(x)=《
   \——  xyz + f(x-1) + abc x> 1

应用到当前问题上来说:
当x=1,函数退出,1既不是质数,也不是合数。
函数调用参数从100开始,f(100),这样就在f函数里面递归往下再调用f(99)。那质数保存在哪里呢?所以需要再加一个参数,f(100,v),函数调用结束之后,v中就是找到的质数了。

当x=100,
f(x,v)
{
}
我们考虑函数怎么实现。
根据前面提到的如何找质数的方法,也就是需要让x遍历v来整除:
foreach( prime in v){
  if( x / prime == 0 ) break;
}
if ( v 被遍历完毕 )  v.pushback(x);  //vector遍历完毕,所有质数都除过了,都除不尽,所以是一个新的质数,加入到vector中去。

我们考虑上面这段算法,要添加到哪里去呢?既然是递归,函数里面肯定要再次调用本函数:
f(x,v)
{
   f(x-1,v);
}
 算法添加到递归调用前面还是后面?如果是前面,当x=100的时候,v就是空的,所以是不行。添加在后面呢?
 f(99,v)会继续调用f(98,v),一直到f(1,v);
 当x=1的时候。函数返回。所以f(1,v)什么都不做,只是返回了。我们考虑返回到上一次调用的时候是什么情况,上一次调用肯定是x=2了。

 我们将寻找质数代码加入到函数中:
f(x,v)
{
   if(x==1) return;
   f(x-1,v);
     寻找找质数代码
}
我们看x=2的时候,函数怎么执行的:
f(2,v)
{

}
此时,v还是空的,从x=100,一直调用到这里的时候,v一直是空的。
f(2,v)
{
   if(x==1) return; -->x=2,不执行。
   f(x-1,v);  --> 调用f(1,v),这个调用满足x==1的条件,直接返回。此时f()递归函数调用终于到底,从底返回了。
     寻找找质数代码 --->将2加入到质数vector中。
}
所以f(2,v)返回的时候,v中已经有一个质数了。此时f(2,v)返回到哪里了?
f(3,v)
{
   if(x==1) return; -->x=2,不执行。
   f(x-1,v);  --> 调用f(2,v),这个调用刚才分析返回了。v中已经有了数据了。
     寻找找质数代码 --->将3加入到质数vector中。
    }

    以此类推,终于回到f(100,v)了。
    100不是质数,不加入到v中,最终f函数也结束了。

    所以递归调用的过程是这样的:

    void f(int x, vector<int> & v)
    {
      if( x==1 ) return ;
        if( x== 2) v.pushback(2) return;

        寻找质数代码片段
        foreach( prime in v){
        }
        ....

        return
    }

    调用:
    vector<int> v;
    f(100,v);

    函数返回后,v中就是质数了。

    请自己理解,我没有写代码。为什么后面我增加了x==2的判断,请自行思考。
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问