بهترین الگریتم برای اعداد اول چیست؟

[KAVEH_RBT]

فکر کنم تمام کسانی که اینجا تو این فروم عضو هستن برای یک بار هم که شده برنامه ای برای بدست آوردن اعداد اول نوشته باشند
همه هم آگاه هستن که انعطاف زیادی برای بهبود الگریتم نداریم
ساده ترین راه برای بدست آوردن یه دامنه از اعداد اول هم تقریبا اینجوریه

for x=1 to n
for x2=2 to x/2
if x/x2 =int(x/x2) then goto lb
next x2
print x
lb:
next x

این کد را فقط نوشتم که حدود کار دستمون باشه
با یه همچین کدی هر چقدر هم که اون رو بهینه کنیم آخرش دو تا حلقه تو در تو داریم و به اعداد بزرگ مثلا حتی 1,000,000 هم رسیدن خیلی زمان بر میشه
پس برای سرعت بالاتر چه میشه کرد؟؟

من خیلی وقتها زمان زیادی را صرف این الگریتم میکنم چون برای من اعداد اول خیلی جالبه.

یکی از چیزهائی که جدیدا پی بردم اینه که:

در حلقه داخلی به جای اینکه تا x/2 را حداکثر x2 قرار بدم جذر x را قرار میدم این خودش خیلی تفاوت سرعت ایجاد میکنه

فعلا تا اینجا کافیه چند تا ترفند دیگه هم یاد گرفتم که سرعت را خیلی بالاتر میبره

الان با این الگوی جدید دارم دامنه اعداد اول 1 تا 1,000,000,000 را بدست میارم تو نزدیک 10 ساعت از 500,000,000 رد شدم تا 15 ساعت دیگه هم تقریبا تموم میشه
الان برنامه من حدود 10000 عدد در ثانیه چک میکنه (افت سرعت خیلی کمه در شروع 16000 بوده)

[SamaPic]

شيوه ي جالبي است.
فكر خلاقانه اي داريد.

[pvza85]

می دونی مبحث کامپیوتینگ و الگوریتم خیلی مبحث هیجان انگیزی هستش:قلب: و اینجوری که معلومه تو خیلی علاقه مندی و کار درست هم همینه که زحمت بکشی، ابدا کنی و تغییری بدی و از تغییرت لذت ببری. همین روال رو ادامه بده.
ولی بهت پیشنهاد می کنم مطالعت رو تو ضمینه الگوریتم بیشتر کنی چون بهت جهت فکری می ده و باعث می شه فکرت باز بشه. (البته منظورم این نیست که خودت فکر کردن رو بزاری کنار، سعی کن کارای دیگران رو یاد بگیری و هر چیزی که می بینه به چالش بکشیش و یه چیزه جدید بهش اضافه کن) الگوریتم های فوق العاده ای تا حالا بوجود اومده که حتی بعد از سالها کار با الگوریتم خوندنشون آدرنالینتو می بره بالا:لبخند: الگوریتم های امنیتی مثل همین الگوریتم RSA که با اعداد اول کار می کنه یا DES یا Rijndael یا الگوریتم های کدینگ و فشرده سازی مثل jpeg یا ogg یا الگوریتم های گرافیکی ... یا الگوریتم های ژنتیک که استفاده ازشون می کنی، معجزه می کنن ولی آخرش نمی فهمی چی شد:قهقهه: این الگوریتم ها خیلین که هر کدوم نتیجه سالها تلاش یک یا چندین متخصص الگوریتم هستش.
بهترین الگوریتم برا پیدا کردن اعداد اول AKS Algorithm هستش، البته گفتن بهترین خیلی سخته ولی جدیدترین هستش و در اغلب مواقع بهترین جواب رو می ده ولی الگوریتم های دیگه هم هستن مثل:
lucas-lehmer
pepin
fermat
solvay-strassen
Miller-Rabin


اینجا رو ببین
http://en.wikipedia.org/wiki/Prime_number

و اینم لینک الگوریتم AKS
http://fatphil.org/maths/AKS/

[KAVEH_RBT]

خوب حالا ترفند بعدی که من استفاده میکنم و این هم تاثیر زیادی در سرعت داره اینه:
من در محاسبه کردن بر همه اعداد کوچکتر از جذر عدد تقسیم نمیکنم فقط اعداد اول کوچکتر از جذر عدد
مثلا در مورد عدد 77 که اول نیست الگریتم من تا جذر 77 یعنی 8.77 در واقع 7 آخرین گزینه اول به حساب میاد تقسیم میکنم و اگه حاصل تقسیم صحیح بود اول نیست به شکل زیر
77/3=25.6
77/5=15.4
77/7=10 اینجا دیگه اول نیست و از حلقه داخلی خارج میشه

[Akam Zandi]

ببخشید ولی خودتون برنامه ای ندارید که بفرستید؟

[saravansoft]

فکر کنم تمام کسانی که اینجا تو این فروم عضو هستن برای یک بار هم که شده برنامه ای برای بدست آوردن اعداد اول نوشته باشند
همه هم آگاه هستن که انعطاف زیادی برای بهبود الگریتم نداریم
ساده ترین راه برای بدست آوردن یه دامنه از اعداد اول هم تقریبا اینجوریه

for x=1 to n
for x2=2 to x/2
if x/x2 =int(x/x2) then goto lb
next x2
print x
lb:
next x

این کد را فقط نوشتم که حدود کار دستمون باشه
با یه همچین کدی هر چقدر هم که اون رو بهینه کنیم آخرش دو تا حلقه تو در تو داریم و به اعداد بزرگ مثلا حتی 1,000,000 هم رسیدن خیلی زمان بر میشه
پس برای سرعت بالاتر چه میشه کرد؟؟

من خیلی وقتها زمان زیادی را صرف این الگریتم میکنم چون برای من اعداد اول خیلی جالبه.

یکی از چیزهائی که جدیدا پی بردم اینه که:

در حلقه داخلی به جای اینکه تا x/2 را حداکثر x2 قرار بدم جذر x را قرار میدم این خودش خیلی تفاوت سرعت ایجاد میکنه

فعلا تا اینجا کافیه چند تا ترفند دیگه هم یاد گرفتم که سرعت را خیلی بالاتر میبره

الان با این الگوی جدید دارم دامنه اعداد اول 1 تا 1,000,000,000 را بدست میارم تو نزدیک 10 ساعت از 500,000,000 رد شدم تا 15 ساعت دیگه هم تقریبا تموم میشه
الان برنامه من حدود 10000 عدد در ثانیه چک میکنه (افت سرعت خیلی کمه در شروع 16000 بوده)
خوب اگه میشه برنامه رو برای استفاده از همه قرار دهید:لبخند: