用递归找素数

Question

请设计3开始按升序找到素数的程序，找100个素数,并从大到小的数字以逗号分隔值的顺序输出。

但是，该程序必须满足以下条件。
·不要使用For，While等循环语法。 （改为使用递归处理）
·加快速度。 （如多线程）### 题目描述

Answer 1

<?php
function digui($a,$b)
{

    if($a%$b == 0) {
        return $a;
    }else {
        if($b == 2) {
            return false;
        }
        return digui($a,$b-1);
    }
}

function test($num,$arr=[])
{
    $res = digui($num,$num-1);

    if(!$res) {
        array_push($arr,$num);
    }

    if (count($arr) == 100)
    {
        //倒xu排列数组
        rsort($arr);
        //implode = 将数组用,切割成字符串 
        echo implode(',',$arr);
        exit();
    }
    $num++; 
    test($num,$arr);
}
test(3,[]);

Answer 2

res = [3]


def isprime(n, i):
    if i == len(res):
        return True
    elif n % res[i] == 0:
        return False
    else:
        return isprime(n, i + 1)


def find(cur):
    if len(res) < 100:
        if isprime(cur, 0):
            res.append(cur)
        cur += 2
        find(cur)


find(5)
print(res)

时间复杂度O(nk), 其中k=100，n为P(k)/2第k个质数，不支持并发