پروژه بزرگ برنامه نویسی

[Steve Jobs]

سلام

می خواهیم اعدادی رو با 2 الی 3 میلیون رقم دریافت کنیم و سپس بررسی کنیم که این عدد اول هست یا نه

همون طور که گفتم، وی بی حرفه ای نمیدونم. اما برای الگوریتمش میتونیم باهم پیش بریم.

عدد اول عددی است که فقط بر یک و خودش قابل تقسیم باشد .

هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی است. (پس برای فهمیدن اینکه عدد اول هست یا نه ، میشه از عکس این موضوع استفاده کرد)

اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد.

دربرنامه نویسی دقیقا از دو نکته اول و دوم تون باهم استفاده میشه.
کاملا این دونکته کاربردیه.
اما نکته آخر را تا حالا نشنیده بودم یا اینکه یادم رفته... خیلی جالبه.

نظر من اینه که برای اعداد بالاتر از 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 نداشته باشه هم مهم نیشت بازم میشه به شیوه های جالب دیگه فقط اعداد اول را ذخیره کرد و زمان پرسش کاربر آماده بهش جواب داد.