پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
نوشته اصلی توسط
mpkahkeshan
سلام به همه دوستان و سروران گرامی. می خواستم یه پروژه بزرگی رو راه اندازی کنم گفتم اینجا مطرح کنم تا توسط همه دوستان پیگیری بشه و إن شاءالله به یه نتیجه خوب برسه. اول از همه بگم که پروژه به زبان وی بی هستش.
می خواهیم اعدادی رو با 2 الی 3 میلیون رقم دریافت کنیم و سپس بررسی کنیم که این عدد اول هست یا نه ( به همین سادگی! البته یه بخشی از کار واقعا ساده است. ولی یه بخش دیگه اش سخت میشه و سختی اش هم به خاطر حجم زیاد کاره) اگر مایل هستید، توضیحات بیشتر رو ارائه بدم تا پروژه رو کلید بزنیم. هر کی مرد این میدونه یا علی همین جا اعلام بکنه.
[movafaghiyat][movafaghiyat][movafaghiyat] [golrooz][golrooz][golrooz] [cheshmak][cheshmak][cheshmak]
با سلام به دوست گلم :»
نمی دونم شاید من اشتباه می کنم ولی توی اعداد بالا مثل همینی که گفتید اگر عدد به 2 و 3 و 5 بخش پذیر نباشد اول است
شما هم یکم حساب کتاب کنید ببینید ایا واقعا درسته ؟؟؟
پاسخ : پروژه بزرگ برنامه نویسی
از وی بی چیزی نمیدونم ................. ولی امیدوارم این 3 جمله زیر بدرد بخوره ...................... [tafakor]
عدد اول عددی است که فقط بر یک و خودش قابل تقسیم باشد .
هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی http://www.codecogs.com/eq.latex?%5Csqrt%7Bn%7D است. (پس برای فهمیدن اینکه عدد اول هست یا نه ، میشه از عکس این موضوع استفاده کرد)
اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد.
موفق باشید [golrooz]
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
نوشته اصلی توسط
radical 1111
از وی بی چیزی نمیدونم ................. ولی امیدوارم این 3 جمله زیر بدرد بخوره ...................... [tafakor]
عدد اول عددی است که فقط بر یک و خودش قابل تقسیم باشد .
هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی
http://www.codecogs.com/eq.latex?%5Csqrt%7Bn%7D است. (پس برای فهمیدن اینکه عدد اول هست یا نه ، میشه از عکس این موضوع استفاده کرد)
اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد.
موفق باشید [golrooz]
با سلام به دوست گلم »
عدد اول مشخص هست چی هست ولی چون عدد میلیونی هست و میلیاردی یک زمان میبره
باید یک راهی پیدا کرد که بشه عدد رو بدون این همه حساب کردن بدست اورد
به عنوان مثال اگه بخوایم عدد 7 رو ببینیم اوله یا نه باید از عدد 2 شروع کنیم به تقسیم کردن تا باقی ماندش 0 بشه
و چون فقط به خودش تقسیم میشه و باقی ماندش 0 میشه عدد اول هست
چون اندازه ی حلقمون زیاد هست باید دنبال ساده ترین راه حل گشت که بالاترین سرعت رو داشته باشه
نظر من اینه که برای اعداد بالاتر از 2 رقم بر 4 عدد 2 و 3 و 5 و 7 تقسیم کنیم اگه تقسیم شد که عدد اول نیست ولی اگه بر این4 تا عدد تقسیم نشد
ولی بازم حساب میکنم این روش من مشکلاتی داره فقط مشکلش وقتی هست که یک عدد اول ضرب در یک عدد اول بشه
به عنوان مثال 11*11 که میشه 121 حالا 121 رو اگر بر این 4 تا عدد تقسیم کنیم میشه اول ولی در صورتی که اول نیست چون به جز خودش بر 11 هم تقسیم میشه
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
نوشته اصلی توسط
NameEly
با سلام به دوست گلم :»
نمی دونم شاید من اشتباه می کنم ولی توی اعداد بالا مثل همینی که گفتید اگر عدد به 2 و 3 و 5 بخش پذیر نباشد اول است
شما هم یکم حساب کتاب کنید ببینید ایا واقعا درسته ؟؟؟
سلام
بايد عدد را به ترتيب به عوانل اول تقسيم كرد تا يكي مانده به خود عدد
اگر باقيمانده يكي از تقصيمها صفر بود اول نيست
البته مطمئن نيستم كه اين عبارتم عينا درست باشه
ولي ي چيزي در همين حدوده
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
نوشته اصلی توسط
محسن آزماینده
سلام
بايد عدد را به ترتيب به عوانل اول تقسيم كرد تا يكي مانده به خود عدد
اگر باقيمانده يكي از تقصيمها صفر بود اول نيست
البته مطمئن نيستم كه اين عبارتم عينا درست باشه
ولي ي چيزي در همين حدوده
میشه بیشتر توضیح بدی ؟
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
میشه بیشتر توضیح بدی ؟
دوستان من فکر این رو کردم. می تونیم از 10 شروع کنیم یعنی اعداد اول کوچکتر از ده رو داریم و داخل دیتابیس ذخیره می کنیم. بعد اعداد بزرگ تر از 10 رو به اعداد اول کوچکتر از 10 تقسیم می کنیم. اگر بخش پذیر نبود ان عدد اول است و به لیست اعداد اول اضافه می شود. در مرحله بعدی باید به اعداد اولی که توی لیست هست تقسیم بشه. همین جور این لیست بزرگ و بزرگ تر میشه و به اون نتیجه دلخواه می رسیم. یعنی پیدا کردن یه عدد اول در حد میلیون رقم. تازه در رقم های بالا می تونیم از قواعد بخش پذیری استفاده کنیم که خیلی آسونتر هستند. مثلا اگر رقم آخر عدد زوج بود بر 2 بخش پذیر است و لازم نیست که خودمون و کامپیوتر رو برای یک تقسیم میلیاردی خسته کنیم. به طور کلی در هر 1000 عدد متوالی مخصوصا در ارقام بالا حدود سه چهارم اعداد(البته محاسبه دقیق نکردم. سر انگشتیه) رو می شه با قواعد ساده بخش پذیری اوت کرد. ولی مشکل اصلی من این نیست. مشکل اینه که از حافظه کامپیوتر برای محاسبه و نگهداری این اعداد نمی شه استفاده کرد(حداکثر 40 رقم) و باید اون ها رو رشته کرد و محاسبات رو رشته ای انجام داد. می خوام به کمک هم یه کلاس تعریف کنیم که این کارو انجام بده.
پاسخ : پروژه بزرگ برنامه نویسی
سلام
نقل قول:
نوشته اصلی توسط
mpkahkeshan
می خواهیم اعدادی رو با 2 الی 3 میلیون رقم دریافت کنیم و سپس بررسی کنیم که این عدد اول هست یا نه
همون طور که گفتم، وی بی حرفه ای نمیدونم. اما برای الگوریتمش میتونیم باهم پیش بریم.[cheshmak]
نقل قول:
نوشته اصلی توسط
radical 1111
عدد اول عددی است که فقط بر یک و خودش قابل تقسیم باشد .
هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی
http://www.codecogs.com/eq.latex?\sqrt{n} است. (پس برای فهمیدن اینکه عدد اول هست یا نه ، میشه از عکس این موضوع استفاده کرد)
اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد.
دربرنامه نویسی دقیقا از دو نکته اول و دوم تون باهم استفاده میشه.
کاملا این دونکته کاربردیه.
اما نکته آخر را تا حالا نشنیده بودم یا اینکه یادم رفته... خیلی جالبه.
نقل قول:
نوشته اصلی توسط
NameEly
نظر من اینه که برای اعداد بالاتر از 2 رقم بر 4 عدد 2 و 3 و 5 و 7 تقسیم کنیم اگه تقسیم شد که عدد اول نیست ولی اگه بر این4 تا عدد تقسیم نشد
ولی بازم حساب میکنم این روش من مشکلاتی داره فقط مشکلش وقتی هست که یک عدد اول ضرب در یک عدد اول بشه
به عنوان مثال 11*11 که میشه 121 حالا 121 رو اگر بر این 4 تا عدد تقسیم کنیم میشه اول ولی در صورتی که اول نیست چون به جز خودش بر 11 هم تقسیم میشه
اینکه فقط به یه سری اعداد خاص تقسیمشون کنیم همه اعداد اول را برامون تولید نمیکنه. باید کاملا بدون محدودیتِ تعداد عناصر چک شده پیش بریم.
نقل قول:
نوشته اصلی توسط
محسن آزماینده
بايد عدد را به ترتيب به عوانل اول تقسيم كرد تا يكي مانده به خود عدد
اگر باقيمانده يكي از تقصيمها صفر بود اول نيست
درسته .
اما میشه به همه اعداد تقسیم کرد به جای تقسیم به عوامل اول.
چون پیدا کردن اعداد اول خودش برای ما سواله.
میشه برای کاهش هزینه اجرا تا یکی مانده به آخری پیش نرویم. تا n/2 امین عنصر پیش بریم. (طبق نکته 2 جناب radical 1111)
نظر من:
فکر نکنم کاری به جز روال عادی وجود داشته باشه.
یعنی تقسیم به همه ی عوامل که دربازه ی [n,n/2] قرار گرفتند و درصورت یک شدن باقی مانده یکی از این تقسیم ها قطع ادامه کار و اعلام مرکب بودن آن. در غیر این صورت اعلام اول بودن آن.
این یعنی باید به اندازه ی نصف عدد حلقه بزنیم.(که این از نظر هزینه بده)
یه کار دیگه اینکه پیش پردازش را پیچیده کنیم اما عوضش هزینه پاسخ سریع بشه!
این طوری:
اگه بدانیم حداکثر عددm میتواند دریافت شود، همه اعداد اول تا اون نقطه را به همون روش بالا بدست بیاریم و به شکل دسته بندی شده ذخیره کنیم .
با استفاده از Hash دسترسی بهشون را آسان و سریع کنیم.
یعنی وقتی از من پرسیده شده آیا عدد k اول است من نمیام حساب کنم آیا این اوله یا نه ، میام به جدول Hashing مراجعه میکنم ببینم اونجا نوشته شده یا نه. یعنی فقط هزینه ی تابع Hash را داریم . زمان اجرا خیلی کم میشه اما هزینه پیش پردازش بالا.
اگه وی بی Hash نداشته باشه هم مهم نیشت بازم میشه به شیوه های جالب دیگه فقط اعداد اول را ذخیره کرد و زمان پرسش کاربر آماده بهش جواب داد.
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
نوشته اصلی توسط
mpkahkeshan
دوستان من فکر این رو کردم. می تونیم از 10 شروع کنیم یعنی اعداد اول کوچکتر از ده رو داریم و داخل دیتابیس ذخیره می کنیم. بعد اعداد بزرگ تر از 10 رو به اعداد اول کوچکتر از 10 تقسیم می کنیم. اگر بخش پذیر نبود ان عدد اول است و به لیست اعداد اول اضافه می شود. در مرحله بعدی باید به اعداد اولی که توی لیست هست تقسیم بشه. همین جور این لیست بزرگ و بزرگ تر میشه و به اون نتیجه دلخواه می رسیم. یعنی پیدا کردن یه عدد اول در حد میلیون رقم. تازه در رقم های بالا می تونیم از قواعد بخش پذیری استفاده کنیم که خیلی آسونتر هستند. مثلا اگر رقم آخر عدد زوج بود بر 2 بخش پذیر است و لازم نیست که خودمون و کامپیوتر رو برای یک تقسیم میلیاردی خسته کنیم. به طور کلی در هر 1000 عدد متوالی مخصوصا در ارقام بالا حدود سه چهارم اعداد(البته محاسبه دقیق نکردم. سر انگشتیه) رو می شه با قواعد ساده بخش پذیری اوت کرد. ولی مشکل اصلی من این نیست. مشکل اینه که از حافظه کامپیوتر برای محاسبه و نگهداری این اعداد نمی شه استفاده کرد(حداکثر 40 رقم) و باید اون ها رو رشته کرد و محاسبات رو رشته ای انجام داد. می خوام به کمک هم یه کلاس تعریف کنیم که این کارو انجام بده.
خب پس شما مشکل الگوریتم ندارید.
آره منم دقیقا به همین موضوع داشتم فکر میکردم.
فکر خوبیه.
پس از اینجا به بعد (نوشتن کد) کار من نیست.[nishkhand](وی بی بلد نیستم[sootzadan])
موفق باشید[golrooz]
پاسخ : پروژه بزرگ برنامه نویسی
نقل قول:
خب پس شما مشکل الگوریتم ندارید.
آره منم دقیقا به همین موضوع داشتم فکر میکردم.
فکر خوبیه.
پس از اینجا به بعد (نوشتن کد) کار من نیست.[nishkhand](وی بی بلد نیستم[sootzadan])
موفق باشید[golrooz]
برای نوشتن کلاسی که لازم داریم می تونیم از شما کمک بگیریم. واقعاً خوشحال می شم اگر شما هم مارو همراهی کنید[golrooz]
