c++ - 再帰関数を使用し、ループを使用せずに素数を示すコード (c++)

Question

以上がタイトルです。
簡単に言えば、私はこれを書いていました。

#include <iostream>
using namespace std;  
int main()  
{ 
    int a,i;  
    cout<<"Enter a number: ";  
    cin>>a;  
    for (i=2;i<=a/2;i++)  
    {  
        if (a%i==0)  
        {  
            cout<<"Its not Prime Number.";  
           system ("pause");  
            return 0;  
        }  
    }  
    cout<<"Its a Prime number.";  
    system ("pause");  
    }   

主なことは、ループを使用せず、再帰関数を使用することです。

Answer 1

主に、 for ループの本体を "int i" をパラメーターとして受け取る関数にすることを検討したいと考えています。次に、関数の先頭に i<=a/2 のテストを配置し、最後に "function(i + 1)" を呼び出します。

Answer 2

コンパイル時の定数値が指定されている場合、コンパイル時に計算も実行できる再帰に基づくソリューションを次に示します。

constexpr bool check_divisibility(int i, int j)
{
    return (j == 1) ? false : 
           ((i % j == 0) ? true : check_divisibility(i, j - 1));
}

constexpr bool is_prime(int i) { return !check_divisibility(i, i / 2); }

クライアントコードでそれを使用する方法は次のとおりです。

#include <iostream>

using namespace std;

int main()
{
    static_assert(is_prime(11), "Error!"); // Computed at compile-time
    int x = 15;
    cout << is_prime(x); // Computed at run-time
}

Answer 3

再帰的な素数性テスト関数は次のとおりです。

int test_prime(unsigned n, unsigned d)
{
    if (n < 2) {
        return 0;
    }

    if (d == 1) {
        return 1;
    } else {
        if (n % d == 0) {
            return 0;
        } else {
            return test_prime(n, d - 1);
        }
    }
}

次のように使用します。

unsigned n;
std::cin >> n;
std::cout << (test_prime(n, n / 2) ? "prime" : "not prime") << "\n";