ورود

View Full Version : تشخیص اول بودن اعداد بزرگ


Azar.099
سه شنبه 10 تیر 1393, 00:06 صبح
سلام دوستان

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

اعداد تا 200 رقم هستند ... و زمان مناسب یعنی در حدود چند ثانیه

میشه راهنماییم کنید

ممنونم.
rahnema1
سه شنبه 10 تیر 1393, 10:12 صبح
سلام
توی کتابخانه gmp پیاده سازی شده
Azar.099
چهارشنبه 11 تیر 1393, 00:14 صبح
با این کتابخونه چطوری میتونم کار کنم ؟
Azar.099
چهارشنبه 11 تیر 1393, 00:23 صبح
نه..
من با اعداد بزرگش کاری ندارم .. الگوریتم برای پیدا کردن اعداد اولش را میخوام پیدا کنم
محمد فدوی
چهارشنبه 11 تیر 1393, 08:49 صبح
چنین برنامه ای خیلی از نظر فنی بحث می طلبه! اول اینکه شما پیاده سازی اعداد ۲۰۰ رقمی رو چطور انجام دادین؟ این میتونه خیلی روی الگوریتم مناسب تاثیر میذاره. من اطلاعاتم زیاد نیست ولی برای برنامه های بررسی اعداد اول توزیع هایی وجود داره که اعداد ۲۰۰ رقمی رو طوری پیاده سازی میکنه که کمترین میزان بار پردازشی اضافه بشه.

از همه ی اینا گذشته برنامه قراره چکار کنه؟ صرفا Primality Test (http://en.wikipedia.org/wiki/Primality_test)؟ (یعنی میخواید یه عدد ۲۰۰ رقمی از کاربر بگیرید و بش بگید اوله یا نه؟!)
یا قراره یه رنج از اعداد رو بگیره و اعداد اولش رو جدا کنه؟ (مثلا غربال اراتستن (http://fa.wikipedia.org/wiki/%D8%BA%D8%B1%D8%A8%D8%A7%D9%84_%D8%A7%D8%B1%D8%A7% D8%AA%D9%88%D8%B3%D8%AA%D9%86) یکی از راه حل های کلاسیک این مسئله ست)
در ضمن من مطمئن نیستم با یه PC ساده بشه در حد چند ثانیه اول بودن یا نبودن یک عدد ۲۰۰ رقمی رو تعیین کرد. چنین پروژه هایی الان در سطح دنیا بصورت Embedded بین چند ابر کامپیوتر انجام میشن!

http://en.wikipedia.org/wiki/Largest_known_prime_number
http://www.sciencedaily.com/releases/2013/02/130213225424.htm
مسعود اقدسی فام
چهارشنبه 11 تیر 1393, 15:20 عصر
اول بودن یه عدد قانون خاصی نداره. به همین دلیل هیچ روش قطعی برای تشخیص اول بودن یه عدد وجود نداره. مگه بخواد با بررسی باقیمانده‌ی تقسیم بر اعداد اول کوچکتر و این دست روشای کلاسیک (مثل اراتستن) حل کنید که برای اعداد خیلی خیلی بزرگ اصلا به صرفه نیست.
برای بررسی اول بودن یه عدد خیلی خیلی بزرگ چند صد رقمی، یه سری آزمونای ریاضی وجود دارن که اگه یه عدد دلخواه ازشون رد بشه به احتمال خیلی خیلی زیاد (نزدیک به یک) اول بودن یا نبودنش مشخص می‌شه. مثلا این لینک رو ببینید:

http://www.wikihow.com/Check-if-a-Number-Is-Prime
این دست محاسباتم معمولا زمان‌بر هستن.