سلام
می خواستم اگه کسی می تونه الگوریتم به روش بازگشتی برای تعیین نمودن اول بودن یا نبودن یک عدد را توضیح بده.
در ضمن شرمنده اگه خواستین کد بذارین به زبان پاسکال نذارین چون من پاسکال بلد نیستم!!!
ممنون.
Printable View
سلام
می خواستم اگه کسی می تونه الگوریتم به روش بازگشتی برای تعیین نمودن اول بودن یا نبودن یک عدد را توضیح بده.
در ضمن شرمنده اگه خواستین کد بذارین به زبان پاسکال نذارین چون من پاسکال بلد نیستم!!!
ممنون.
سلام
این برنامه حداقل 5-4 تا الگوریتم مختلف داره. من الان 2 تا الگوریتم رو حضور ذهن دارم، ولی چون کی برد فارسی ندارم و تایپ فارسی برام سخته یکیشو میگم، اگر شد و تونستم تایپ کنم دومیشم به چشم.
راه حل خیلی ساده ست، یه حلقه بازگشتی بنویس که عدد n (عدد مورد نظر) را به ترتیب بر اعداد 2 تا رادیکال n تقسیم کند و در اولین موردی که تقسیم پذیر بود از حلقه خارج شود. اگر هم مقسوم علیه از رادیکال n بزرگتر شد از حلقه خارج شده مقدار n را برگرداند. این الگوریتم در واقع الگوریتم prime number واقعی نیست، بلکه الگوریتم پیدا کردن کوچکترین مقسوم علیه است. ولی در این مورد نیز کاملا کاربردی ست.
یکی از الگوریتم های اصلی این برنامه الگوریتم فرمت Fermat Test است که در سال 1637 میلادی توسط Pierre de Fermat ابداع گردید. اگه بتونم اونم می ذارم.
دوست عزیز این روش بازگشتی نیست..زمان مصرفیش جذر n هست و فکر کنم همون چیزی که این دوستمون مدنظرش بود ...
void findPrimes(bignum topCandidate)
{
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++;
}
}
اگر بازگشتیش کنی زمان مصرفیش بسیار زیاد می شه و برای اعداد بزرگ نه تنها جواب نمی ده بلکه خودت پشیمون می شی از اجرای برنامه ..ولی اگر خواستی بگو برات می ذارم اینجا ...
حالا من یه سوال دارم آیا کسی الگوریتم بهتری (با زمان مصرفی کمتری) سراغ داره ؟
سام آقای aliji اول ازتون ممنون من اون چیزی که شما گفتین رو بلدم اما من الگوریتم بازگشتی می خوام!!!
--------------------
یک روش دیگر هم برای این کار هست با توجه به تعریف زیر:
عددی اول هست که بر هیچ کدام از اعداد اول کوچکتر از خودش بخش پذیر نباشد
این از همون روش استفاده می کنه ولی بازگشتی !!
function Prime( n)
if IsPrime(n,2) then
return true
else
return false
end
function IsPrime( n, trialDivisor)
if ( n % trialDivisor =0)
return false
else if ( trialDivisor * trialDivisor > n)
return true
else
return IsPrime( n, trialDivisor+1)
end
و این هم یه روش دیگه غیر بازگشتی :
function IsPrime( n)
if ( (n-1)!+1 % n =0)
return true
else return false
end
و این هم ابتدائی ترین روش با بدترین زمان مصرفی !!
function Prime( n)
if IsPrime(n,2) then
return true
else
return false
end
function IsPrime( n, trialDivisor)
if ( n % trialDivisor = 0 )
return false
else if ( trialDivisor>=n)
return true
else return IsPrime( n, trialDivisor+1)
end