آموزش پیدا کردن n عدد اول در سی شارپ (سورس کد)

[™Ali]

سلام خدمت دوستان
یه چند روزی بود داشتم رو نحوه پیدا کردن n عدد اول فکر می کردم که بالاخره یه راه حل خوب پیدا کردم!

اونم استفاده از دو حلقه For و دو حلقه Foreach به شکل زیر بود:
توضیح : عددی که فقط بر خودش و یک بخش پیر باشد یک عدد اول است برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

}

            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 تا بود! برنامه تا محاسبه عدد یک میلیون هم هنگ نمی کنه!
به زودی پروژه کار در تاپیک مربوطه گذاشته میشه.
هدف از ایجاد تاپیک جداگانه درخواست از دوستان است که اگر راه حل بهتری سراغ دارند اینجا اعلام کنند.
با تشکر علی برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[ravegoat]

با سلام!

علی جان، من زیاد از CS سر در نمیارم.برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
فکر کنم سورسی که گذاشتی این جوری عمل می کنه:

1- یه عدد رو از جعبه متنی می گیره.
2-اون عدد رو تفکیک می کنه.
3-تک تک اعداد تفکیک شده رو به اعداد طبیعی کوچک تر از 500 تقسیم می کنه.
4-اگر بر هیچ یک از اعداد کوچک تر از 500 بخش پذیر نباشه (به جز خودش)، عدد تفکیک شده اول محسوب شده و وارد جعبه لیست میشه.

استفاده از الگوریتم تقسیم برای اعداد کوچک مفیده نه برای عدد 100000 ( چه برسه به یک میلیون ).برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

در ضمن یه چیزی؛ هنگ کردن برنامه بسته به نوع سیستم متفاوت هستش. برای رایانه من این سورس روی صد هزار هنگ می کنه؛ دلیل هم واضح است: پایین بودن منابع سخت افزاری !


یک سوال هم داشتم:
آیا تو این سورس به ازای هر عدد یه متغیر (متغیر دارای بعد) تعریف می شه؟! یا این که من دارم اشتباه می کنم...
تعریف زیاد متغیر باعث اشغال رم و کاهش سرعت برنامه می شه. با دو تا متغیر بدون بعد هم میشه این برنامه رو اجرا کرد.برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید


داشت یادم می رفت...
برای شروع سورس هایی که گذاشتی فوق العاده است.برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[ravegoat]

من یه راه دیگه می گم که سرعت کد رو بسیار بالا می بره:

علی جان عدد 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 غربال اراتستن رو تهیه کردم (خیلی ساده استبرای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید ):

http://pcnetwork.ir/showpost.php?p=146039&postcount=16

البته باز هم این روش برای اعداد بزرگ کارآمد نیست.
به طور کلی باید یه مطالبی رو در مورد نظریه ی اعداد فرابگیری. با نظریه اعداد می تونی الگوریتم هایی طراحی کنی که خیلی سریع تر عمل می کنند.

امیدوارم دوستان دیگه، راه حل هایی بهتری ارئه بدند.برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

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

[MoBiN.R]

البته میشد بدون آرایه و حلقه foreach هم پیاده سازی کرد این برنامرو .. در ضمن آرمین جان کاملا درست میگین این برنامه برای اعداد بزرگ اصلا خوب نیست چون اصلا اعداد بزرگ توی محدوده متغیر Integer جا نمیگیرن .. در اینصورت باید عدد وارد شده رو با مثل الگوریتم خواندن رشته در C که رشته توی آرایه قرار میگرفت اعداد رو خوند ..

[™Ali]

سلام خدمت دوستان عزیز برنامه نویس برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

آرمین جان یه اشتباه کوچیک تو توضیح پست دوم داشتی :
برنامه میاد اعداد اون Range رو که بهش دادم وارد ListBox می کنه (تمام اعداد مثلا تا 100 هزار) بعد شروع به تقسیم می کنه اگر هر عددی از اون حلقه For عبور کرد از لیست پاک می کنه! شرط حلقه For هم اینه که عدد باقی مانده صفر داشته باشه!
تا 100 هزار تعداد اعداد اول رو به طور کاملا دقیق به دست میاره ولی بالاتر ممکنه چند تا عدد جا بذاره! برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

یا 211 : جذر 211 تقریبا" 14/5 هستش. اعداد اول کوچک تر یا مساوی 14 عبارت اند از 2 ، 3 ، 5 ، 7 ، 11 ، 13 . 211 بر هیچ یک از این شش عدد اول بخش پذیر نیست پس 211 عدد اول است.

روش بسیار عالیه برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید
ولی مشکل اینه که باز اون اعداد اول پایین تر از مثلا 200 رو چجوری میشه گیر آورد تا تقسیم کرد!

آیا تو این سورس به ازای هر عدد یه متغیر (متغیر دارای بعد) تعریف می شه؟! یا این که من دارم اشتباه می کنم...

کلا تو اون فرمول دو آرایه تعریف میشه و آرایه ها میاد و عدد ها رو میگیرن ! (به وسیله حلقه For عددها در آرایه جاگذاری میشن ) توضیح بیش تر خواستی در خدمتم!

البته میشد بدون آرایه و حلقه foreach هم پیاده سازی کرد این برنامرو .. در ضمن آرمین جان کاملا درست میگین این برنامه برای اعداد بزرگ اصلا خوب نیست چون اصلا اعداد بزرگ توی محدوده متغیر Integer جا نمیگیرن

والا مبین جان بدون حلقه فکری به ذهنم نرسید!
متغیر int میتونه تا 2147483647 رو در خودش جا بده. اگر uInt تعریفش کنیم میشه 4294967295 ! اگر هم uLong تعریفش کنیم میشه 18446744073709551615 !
مقدار خیلی زیادی ولی بازم محدوده! مگر بریم سراغ decimal که دیگه کلا منابع سیستم تلف میشه برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

در اینصورت باید عدد وارد شده رو با مثل الگوریتم خواندن رشته در C که رشته توی آرایه قرار میگرفت اعداد رو خوند ..

بازم نمیشه! چون عدد باید دوباره از string به int تبدیل بشه تا عملیات ریاضی روش انجام بشه! برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

نمایی از برنامه نهایی که نوشتم. محاسبه 100 هزار عدد اول رو تموم کرده (تعداد رو هم نوشته!) :
محاسبه حدود 15 ثانیه طول کشید.....

برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

با تشکر علی برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[MoBiN.R]

درسته علی جان .. دیگه رقمی بالاتر از یه عدد 20 رقمی یه کم خارج از منطق هست ( مگر اینکه سر کاری باشه برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید ) ... در ضمن تا الانشم کلی تایمینگ سیستم برای حساب کردن همه اعداد اول تا 20 رقم ، تلف میشه ..

[™Ali]

سلام

مدت خیلی زیادی که برنامه قبلی رو یک آپدیت کلی کردم و تا الان وقت نکردم واستون بذارم.

تغییرات زیادی رو توش دادم، از جمله :

- نوشتن یک فایل Log در پایان کار
- محدوده سازی (Scope) بسیار دقیق تر
- پیدا کردن ب.م.م و ک.م.م اعداد
- پیدا کردن تمام فاکتورهای یک عدد
- کد بهینه تر
- محاسبه زمان اجرا
- و ...

به نظر خودم فعلا این یکی از بهترین و قوی ترین برنامه های هست که برای پیدا کردن اعداد اول نوشته شده. کاملا انحصاریه برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

سورس کد واسه علاقه مندان ضمیمه شد. فایل EXE واسه دوستانی که نمی تونن کامپایل کنند هم ضمیمه شد.برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

موفق باشید.

[ravegoat]

سلام!

اين سورس چقدر امكانات داره؟! آب هويج هم ميگيره؟!! بدون شوخي واقعا" برنامه ي خوبيه...تبريك مي گم.

علي جان البته خودت استادي ولي من يه پيشنهاد دارم كه به جاي ليست اعداد اول در كلاس FirstPrime؛ از يه الگوريتمي استفاده بشه كه با توجه به بازه ي Scope، خودش ليست اعداد ول رو توليد كنه و براساس اون اعداد موجود در بازه رو تفكيك كنه. اين جوري به نظرم بهتره و مي تونه سريع تر هم باشه!

يه مقدار سورس تو تغيير دادم تا روش اشاره شده رو بتونم پياده سازي كنم (البته كچل شدم تا تونستم با سي شارپ كد شو بنويسمبرای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید ). پروژه رو هم پيوست كردم برای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید .

به خاطر اشتراك سورس هم ممنون.
آرمينبرای مشاهده این لینک/عکس می بایست عضو شوید ! برای عضویت اینجا کلیک کنید

[™Ali]

آب هویج که نه! ولی خاکشیر داره :D

من خودم اول یه کد نوشتم و اعداد اول رو استخراج کردم، بعد وارد کلاس FirstPrime کردم.

تنها مشکل اینه که :

- هر چه تعداد اعداد واسه تقسیم بالا بره، طبیعتا برنامه دقیق تر میشه ولی وقت بیش تری رو واسه پردازش میطلبه.

- همیشه چند میلی ثانیه واسه Generate کردن لیست اولیه اعداد اول برنامه زمان میبره.


خب این شد که گفتیم، لقمه رو خودمون بذاریم تو دهن برنامه.

ممنون از سورس. بررسیش می کنیم. (راستی این که ورژن قبلیه Prime Numbers هست !)