سلام خدمت دوستان
یه چند روزی بود داشتم رو نحوه پیدا کردن n عدد اول فکر می کردم که بالاخره یه راه حل خوب پیدا کردم!
اونم استفاده از دو حلقه For و دو حلقه Foreach به شکل زیر بود:
توضیح : عددی که فقط بر خودش و یک بخش پیر باشد یک عدد اول است :1. (38):
}
int input ;
int.TryParse(txtInput.Text, out input);
int[] Numbers = new int[input];
int[] Divide = new int[500];
for (int x = 2 ; x < input; x++)
{
Numbers[x] = x;
}
for (int x = 0; x < 500; x++)
{
Divide[x] = x + 2 ;
}
foreach ( int x in Numbers )
{
listBox1.Items.Add(x + " یک عدد اول است.");
foreach (int m in Divide)
{
if (x % m == 0 && x != m)
{
listBox1.Items.Remove(x + " یک عدد اول است.");
Application.DoEvents();
مثلا تا عدد 10000 محاسبه کردم تعداد اعداد اول 1229 تا بود! برنامه تا محاسبه عدد یک میلیون هم هنگ نمی کنه!
به زودی پروژه کار در تاپیک مربوطه (Only the registered members can see the link)گذاشته میشه.
هدف از ایجاد تاپیک جداگانه درخواست از دوستان است که اگر راه حل بهتری سراغ دارند اینجا اعلام کنند.
با تشکر علی :give_rose:
ravegoat
26-06-09, 09:06
با سلام!
علی جان، من زیاد از CS سر در نمیارم.:1. (28):
فکر کنم سورسی که گذاشتی این جوری عمل می کنه:
1- یه عدد رو از جعبه متنی می گیره.
2-اون عدد رو تفکیک می کنه.
3-تک تک اعداد تفکیک شده رو به اعداد طبیعی کوچک تر از 500 تقسیم می کنه.
4-اگر بر هیچ یک از اعداد کوچک تر از 500 بخش پذیر نباشه (به جز خودش)، عدد تفکیک شده اول محسوب شده و وارد جعبه لیست میشه.
استفاده از الگوریتم تقسیم برای اعداد کوچک مفیده نه برای عدد 100000 ( چه برسه به یک میلیون ).:whistle:
در ضمن یه چیزی؛ هنگ کردن برنامه بسته به نوع سیستم متفاوت هستش. برای رایانه من این سورس روی صد هزار هنگ می کنه؛ دلیل هم واضح است: پایین بودن منابع سخت افزاری !
یک سوال هم داشتم:
آیا تو این سورس به ازای هر عدد یه متغیر (متغیر دارای بعد) تعریف می شه؟! یا این که من دارم اشتباه می کنم...
تعریف زیاد متغیر باعث اشغال رم و کاهش سرعت برنامه می شه. با دو تا متغیر بدون بعد هم میشه این برنامه رو اجرا کرد.:wink:
داشت یادم می رفت...
برای شروع سورس هایی که گذاشتی فوق العاده است.:1. (10):
ravegoat
26-06-09, 09:06
من یه راه دیگه می گم که سرعت کد رو بسیار بالا می بره:
علی جان عدد 100 رو در نظر بگیر. برای این که متوجه بشویم که این عدد اول هست یا نه، جذر عدد رو به دست میاریم. جذر 100 برابر 10 است. اعداد اول کوچک تر یا مساوی 10 عبارت اند از 2 ، 3 ، 5 ، 7 . حالا 100 را بر تک تک این اعداد تقسیم می کنیم. اگر بر یکی از این ها بخش پذیر بود اول نیست. 100 بر 2 بخش پذیره پس اول نیست!
یا 211 : جذر 211 تقریبا" 14/5 هستش. اعداد اول کوچک تر یا مساوی 14 عبارت اند از 2 ، 3 ، 5 ، 7 ، 11 ، 13 . 211 بر هیچ یک از این شش عدد اول بخش پذیر نیست پس 211 عدد اول است.
متوجه شدی که چقدر ساده است. این عمل غربال گری که به غربال اراتستن معروفه باعث می شه که تعداد گردش ها خیلی خیلی کم بشه. من یک سورس VB.Net غربال اراتستن رو تهیه کردم (خیلی ساده است:cool:):
Only the registered members can see the link
البته باز هم این روش برای اعداد بزرگ کارآمد نیست.
به طور کلی باید یه مطالبی رو در مورد نظریه ی اعداد فرابگیری. با نظریه اعداد می تونی الگوریتم هایی طراحی کنی که خیلی سریع تر عمل می کنند.
امیدوارم دوستان دیگه، راه حل هایی بهتری ارئه بدند.:1. (26):
موفق باشی
آرمین:11():
MoBiN.R
26-06-09, 10:24
البته میشد بدون آرایه و حلقه foreach هم پیاده سازی کرد این برنامرو .. در ضمن آرمین جان کاملا درست میگین این برنامه برای اعداد بزرگ اصلا خوب نیست چون اصلا اعداد بزرگ توی محدوده متغیر Integer جا نمیگیرن .. در اینصورت باید عدد وارد شده رو با مثل الگوریتم خواندن رشته در C که رشته توی آرایه قرار میگرفت اعداد رو خوند ..
™Ali
26-06-09, 11:37
سلام خدمت دوستان عزیز برنامه نویس :1. (21):
آرمین جان یه اشتباه کوچیک تو توضیح پست دوم داشتی :
برنامه میاد اعداد اون Range رو که بهش دادم وارد ListBox می کنه (تمام اعداد مثلا تا 100 هزار) بعد شروع به تقسیم می کنه اگر هر عددی از اون حلقه For عبور کرد از لیست پاک می کنه! شرط حلقه For هم اینه که عدد باقی مانده صفر داشته باشه!
تا 100 هزار تعداد اعداد اول رو به طور کاملا دقیق به دست میاره ولی بالاتر ممکنه چند تا عدد جا بذاره! :1. (38):
یا 211 : جذر 211 تقریبا" 14/5 هستش. اعداد اول کوچک تر یا مساوی 14 عبارت اند از 2 ، 3 ، 5 ، 7 ، 11 ، 13 . 211 بر هیچ یک از این شش عدد اول بخش پذیر نیست پس 211 عدد اول است.روش بسیار عالیه :1. (40):
ولی مشکل اینه که باز اون اعداد اول پایین تر از مثلا 200 رو چجوری میشه گیر آورد تا تقسیم کرد!
آیا تو این سورس به ازای هر عدد یه متغیر (متغیر دارای بعد) تعریف می شه؟! یا این که من دارم اشتباه می کنم...
کلا تو اون فرمول دو آرایه تعریف میشه و آرایه ها میاد و عدد ها رو میگیرن ! (به وسیله حلقه For عددها در آرایه جاگذاری میشن ) توضیح بیش تر خواستی در خدمتم!
البته میشد بدون آرایه و حلقه foreach هم پیاده سازی کرد این برنامرو .. در ضمن آرمین جان کاملا درست میگین این برنامه برای اعداد بزرگ اصلا خوب نیست چون اصلا اعداد بزرگ توی محدوده متغیر Integer جا نمیگیرن
والا مبین جان بدون حلقه فکری به ذهنم نرسید!
متغیر int میتونه تا 2147483647 رو در خودش جا بده. اگر uInt تعریفش کنیم میشه 4294967295 ! اگر هم uLong تعریفش کنیم میشه 18446744073709551615 !
مقدار خیلی زیادی ولی بازم محدوده! مگر بریم سراغ decimal که دیگه کلا منابع سیستم تلف میشه :1. (38):
در اینصورت باید عدد وارد شده رو با مثل الگوریتم خواندن رشته در C که رشته توی آرایه قرار میگرفت اعداد رو خوند ..بازم نمیشه! چون عدد باید دوباره از string به int تبدیل بشه تا عملیات ریاضی روش انجام بشه! :yes:
نمایی از برنامه نهایی که نوشتم. محاسبه 100 هزار عدد اول رو تموم کرده (تعداد رو هم نوشته!) :
محاسبه حدود 15 ثانیه طول کشید.....
Only the registered members can see the link
با تشکر علی :11():
MoBiN.R
26-06-09, 11:58
درسته علی جان .. دیگه رقمی بالاتر از یه عدد 20 رقمی یه کم خارج از منطق هست ( مگر اینکه سر کاری باشه Only the registered members can see the link ) ... در ضمن تا الانشم کلی تایمینگ سیستم برای حساب کردن همه اعداد اول تا 20 رقم ، تلف میشه ..
™Ali
10-09-11, 09:20
سلام
مدت خیلی زیادی که برنامه قبلی رو یک آپدیت کلی کردم و تا الان وقت نکردم واستون بذارم.
تغییرات زیادی رو توش دادم، از جمله :
- نوشتن یک فایل Log در پایان کار
- محدوده سازی (Scope) بسیار دقیق تر
- پیدا کردن ب.م.م و ک.م.م اعداد
- پیدا کردن تمام فاکتورهای یک عدد
- کد بهینه تر
- محاسبه زمان اجرا
- و ...
به نظر خودم فعلا این یکی از بهترین و قوی ترین برنامه های هست که برای پیدا کردن اعداد اول نوشته شده. کاملا انحصاریه :1. (35):
Only the registered members can see the link (Only the registered members can see the link)
سورس کد واسه علاقه مندان ضمیمه شد. فایل EXE واسه دوستانی که نمی تونن کامپایل کنند هم ضمیمه شد.:love:
موفق باشید.
ravegoat
10-09-11, 21:00
سلام!
اين سورس چقدر امكانات داره؟! آب هويج هم ميگيره؟!! بدون شوخي واقعا" برنامه ي خوبيه...تبريك مي گم.
علي جان البته خودت استادي ولي من يه پيشنهاد دارم كه به جاي ليست اعداد اول در كلاس FirstPrime؛ از يه الگوريتمي استفاده بشه كه با توجه به بازه ي Scope، خودش ليست اعداد ول رو توليد كنه و براساس اون اعداد موجود در بازه رو تفكيك كنه. اين جوري به نظرم بهتره و مي تونه سريع تر هم باشه!
يه مقدار سورس تو تغيير دادم تا روش اشاره شده رو بتونم پياده سازي كنم (البته كچل شدم تا تونستم با سي شارپ كد شو بنويسم:lol:). پروژه رو هم پيوست كردم :wink:.
به خاطر اشتراك سورس هم ممنون.
آرمين:give_rose:
™Ali
10-09-11, 21:34
آب هویج که نه! ولی خاکشیر داره :D
من خودم اول یه کد نوشتم و اعداد اول رو استخراج کردم، بعد وارد کلاس FirstPrime کردم.
تنها مشکل اینه که :
- هر چه تعداد اعداد واسه تقسیم بالا بره، طبیعتا برنامه دقیق تر میشه ولی وقت بیش تری رو واسه پردازش میطلبه.
- همیشه چند میلی ثانیه واسه Generate کردن لیست اولیه اعداد اول برنامه زمان میبره.
خب این شد که گفتیم، لقمه رو خودمون بذاریم تو دهن برنامه.
ممنون از سورس. بررسیش می کنیم. (راستی این که ورژن قبلیه Prime Numbers هست !)