الگوریتم یافتم اعداد اول با زمان مصرفی Logn

[manager]

سلام


Problem : Use Wilson's theorem (n is prime if and only if a divisor of (n-1)!+1), Newton's binomial theorem, and the divide-and-conquer technique to design an algorithm capable of deciding in a time in the order of logn, give an integer n, whether or not n is prime.


این طور که من از این مسئله متوجه شدم باید الگوریتمی طراحی کنیم که با استفاده از تئوری ویلسون و دوجمله ای نیوتن ،اول بودن اعداد را بررسی کنیم در زمان مصرفی Logn.

اگر در این رابطه می تونید کمکم کنید ممنون می شم.

[manager]

من خودم یه الگوریتم پیدا کردم که زمان مصرفیش جذر n هست :



bignum candidate = 2;
while(candidate <= topCandidate)
{
bignum trialDivisor = 2;
int prime = 1;
while(trialDivisor * trialDivisor <= candidate)
{
if(candidate % trialDivisor == 0)
{
prime = 0;
break;
}
trialDivisor++;
}
if(prime) printPrime(candidate);
candidate++;
}

,ولی این اون چیزی نیست که من می خوام !!!!
سوال اینجاست که دو جمله ای نیوتون چه ربطی به این مسئله داره !!