素数かどうかを判断する

本プログラムは二次探知定理を採用し、実現コードは以下の通りである.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
void power(unsigned long a,unsigned long p,unsigned long n,unsigned long &result , bool &composite)
{
    unsigned long x;
    if(p == 0)  result = 1;
    else
    {
        power(a, p/2, n, x, composite);
        result = (x * x) % n;
        if((result  == 1) && (x != 1) && (x != n - 1))
            composite = true;
        if((p % 2) == 1)
            result = (result * a ) % n;
    }
}
bool check(unsigned long n,unsigned int k)
{
    unsigned long a,result;
    bool composite=false;
    if(n==1)
    {
        return false;
    }
    for(unsigned int i=1; i<k; i++)
    {
        srand((unsigned)time(NULL));
        a=rand() % (n-3)+2;
        power(a,n-1,n,result,composite);
        if(composite||(result!=1))
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int num,tmp;
    cin>>num;
    for(int i=0; i<num; i++)
    {
        cin>>tmp;
        if(check(tmp,10))
        {
            cout<<tmp<<"   "<<endl;
        }
        else
        {
            cout<<tmp<<"   "<<endl;
        }
    }
    return 0;
}