سلام!
به تازگی برای یه کاری احتیاج به ساختن یه دیتاست عظیم اعداد اول از ۱ تا ۱ میلیون بودم. خب ساده است، ولی اجرا کردن کدی که دیتاست رو می ساخت ۳ دقیقه طول می کشید؛ و امروز یه راه‌حل پیدا کردم که توی ۸ ثانیه اون کار رو انجام می داد! خب شروع کنیم!
اولین راه حل برای اثبات اینکه یه عدد اول یا نه اینه که اینجوری بنویسیمش:
خیلی تمیز می گیم یه تابع داریم که یه n رو می گیره، بعد از ۲ تا خود n-1 حلقه بزن و اگه بخش پذیر بود False بده اگه آخرشم تموم شد یه True بده. آخرشم برای تست یه عدد اول بزرگ مثل ۱۰۰ میلیون و هفت گذاشتیم تا تست کنیم سرعتش رو! از دستور time تو یونیکس برای گرفتن زمان اجرا شدنش استفاده می کنیم:
برای یه عدد ۹.۷ ثانیه ثبت کرد که اصلا جالب نیست(البته اینکه کد پایتونه بی تاثیر نیست) برای همین میریم به راه حل دوم.
خب این کد رو بیشتر از همه توی جا های مختلف دیدم. می گوییم که به جای اینکه تا n-1 حلقه بزنی تا n/2 حلقه بزن، که منطقیه. فقط چون ممکنه خارج قسمت اعشار شه اون رو عدد صحیح می کنیم به علاوه یک می کنیم:
خب ببینیم چقدر سریعه:
باز هم جالب نیست اما بهتره. حدودا نصف قبلی.
حتما یکی از شمارنده های یک عدد، کوچکتر مساوی از رادیکال اون عدده چرا؟
این رو در نظر داشته باشید:
m*n = a
می گیم که جفتشون از رادیکال عدد a بزرگترن:
m>sqrt(a)
n>sqrt(a)
پس:
m*n > sqrt(a) * sqrt(a)
در نتیجه:
m*n > a
که تناقض داره با داده اولیه! پس حتما یکی از شمارنده هاش از رادیکال کوچیکتره:
چون رادیکالش ممکنه اعشار بشه صحیحش می کنیم. اون +۱ هم بخاطر خاصیت range هستش که تا -1 جلو میره.
خب ببینیم چقدر سریعه:
اختلاف وحشتناکی داره با اولی یعنی 243 برابر اولی و 127 برابر دومی!!
خیلی سریع هستش. پس اگه یه روز کار شما به اعداد اول خورد حتما از این راه استفاده کنید.
خیلی ممنون که وقت گذاشتید و خوندید. اگه سوالی دارید لطفا کامنت کنید و ممنون میشم اگه لایک کنید :)
