اعداد اول

در متفرقه

یکی از قشنگ ترین و زیباترین مبحاث ریاضی نظریه اعداده به نظر من ،جایی که آدمی می تونه چالش های ذهنی خودش رو آزادانه مطرح کنه بدونه اینکه واقعاً بخواد به سرنوشت اون تفکرش فکر کنه ، جایی که به مغز اجازه میدیم از انتزاعی بودن بیش از حد نترسه و جایی که یاد می گیریم با دانسته های قبلیمون بازی کنیم

 

یکی از مهم ترین مباحثی که در نظریه اعداد مطرح میشه بحث مربوط به اعداد اوله که امروزه در دنیای کامپیوتر هم نقش به سزایی پیدا کرده پس بریم که یه گره ای بزنیم بین این دو تا رشته تا بعداً اگه عمری باقی بود هی این گره رو کلفت تر و قوی ترش کنیم

 

و اما عدد اول چیه؟

به عدد طبیعی ای که فقط بر یک و خودش بخش پذیر باشه می گیم عدد اول

ولی خب یه جور دیگه هم می تونیم بگیم

دو عدده اوله

هر عدد  طبیعی بزرگتر از دو که به اعداد کوچکتر (به غیر از یک) از خودش بخش پذیر نباشه اوله

مثلاً

سه به دو بخش پذیر نیست پس اوله

چهار به سه بخش پذیر نیست ولی به دو بخش پذیره پس اول نیست

پنج به چهار و سه و دو بخش پذیر نیست پس اوله

شش به پنج بخش پذیر نیست به چهار هم نیست ولی به سه و دو بخش پذیره پس اول نیست

هفت به شیش و پنج و چهار و سه و دو  بخش پذیر نیست پس اوله

و الی آخر

خب حالا بخواهیم یه روش کامپیوتری داشته باشیم که تشخیص بدیم یه عدد اوله باید کار ساده ای باشه فقط کافیه تعریف بالا رو به یک الگوریتم تبدیل کنیم و کدش رو بزنیم

خب من اینجا یه کد تو سی پلاس پلاس زدم که می تونیم تو کار های آینده بهش مراجعه کنیم

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef unsigned long long Int64;
  5.  
  6. void is_prime(Int64 num){
  7. bool prime=true;
  8.  
  9. if(num==1){
  10. prime=false;
  11. }
  12.  
  13. for(Int64 i=2;i<num;i++){
  14. if(num%i==0){
  15. prime=false;
  16. break;
  17. }
  18.  
  19. }
  20.  
  21. if(prime){
  22. cout<<"YES\n";
  23. }else{
  24. cout<<"NO\n";
  25. }
  26.  
  27. }
  28. /*********/
  29. int main(){
  30.  
  31. is_prime(1);
  32. is_prime(2);
  33. is_prime(3);
  34. is_prime(6);
  35. is_prime(11);
  36. is_prime(13);
  37. is_prime(15);
  38.  
  39. return 0;
  40. }

 

و اما این کد چی کار می کنه

فقط تابع is_prime مهمه

 

می بینید که یه متغییر از نوع bool تعریف کردیم که در ابتدا مقدار ش true هست

اگه عدد مورد نظر یک باشه که اول نیست (یادم رفته بود بگم که یک جز اعداد اول حساب نمیشه :دی) اگه عدد دو باشه که شرط داخل for درست در نمیاد و حلقه اجرا نمیشه و متغیر prime مقدارش true می مونه و دو رو به عنوان عددی اول معرفی می کنه

حالا فرض کنیم که num از دو هم بزرگتر باشه اون وقت تنها در صورتی مقدار prime  به false تغییر نمی کنه که شرط num%i==0 هیچ گاه بر قرار نشه و این یعنی هیچ عدد کوچکتر از num ای وجود نداشته باشه که num رو عاد کنه (num به اون بخش پذیر باشه) و این دقیقاً همون تعریفی هست که در بالا ارائه شد

در ضمن وقتی شرط num%i==0 برای یک بار درست بیاد دیگه عدد مورد نظر اول نیست و بعد اون لازم نیست که اجرای حلقه ادامه پیدا کنه برای همین توی اون شرط بعد از مقدار دهی متغیر prime به false از دستور break استفاده کردم

 

خب اگه یه نموره با درسایی مثل ساختمان داده یا طراحی الگوریتم یا امثال اینا  آشنایی داشته باشید به راحتی متوجه میشید که زمان اجرای کد  قبلی از مرتبه O(n)dهست و  معمولاً اونایی که تازه وارد دنیای الگوریتم شدن با خودشون می گن : ای ول اوی ان،خیلی خوبه اصن برنامه اوی ان باشه یعنی خیلی توپه و غیره و غیره ولی این تفکر کاملاً اشتباهه و مرتبه اجرایی برنامه باید متناسب با مسئله ای باشه که قراره حلش کنیم مثلاً اگه بخواهیم یه صد هزار تا عدد صحیح رو مرتب کنیم و یه الگوریتم مرتبه O(N)d یا مرتبه O(NlogN)d داشته باشیم خوبه ولی اینجا نظریه اعداده خیلی وضع از اونی که فکر می کنید بد تره :دی ، به نظرتون با همین برنامه قبلی اول بودن چه اعدادی رو می تونیم توی یه زمان مناسب چک کنیم؟؟ اگه اینجا یه عدد اول ۲۰ رقمی رو بخواهیم چک کنیم حلقه مورد نظر باید به اندازه همین عدد تقریباً اجرا شه و این یعنی خیلی :دی ، برای اینکه موضوع بهتر جا بیفته همین حرف رو با مثال اجرا می کنیم

 

به کد زیر دقت کنید

  1. #include <iostream>
  2. #include <time.h>
  3. using namespace std;
  4.  
  5. typedef unsigned long long Int64;
  6.  
  7. void is_prime(Int64 num){
  8.  
  9. bool prime=true;
  10.  
  11. if(num==1){
  12. prime=false;
  13. }
  14.  
  15. for(Int64 i=2;i<num;i++){
  16. if(num%i==0){
  17. prime=false;
  18. break;
  19. }
  20.  
  21. }
  22.  
  23. if(prime){
  24. cout<<"YES\n";
  25. }else{
  26. cout<<"NO\n";
  27. }
  28.  
  29. }
  30. /*********/
  31. int main(){
  32.  
  33. time_t start,end;
  34.  
  35. Int64 num1=13,num2=1069,num3=29005541,num4=334214459,
  36. num5=3780008329,num6=29996224275833;
  37.  
  38. time(&start);
  39. is_prime(num1);
  40. time(&end);
  41. cout<<difftime(end,start)<<"\n";
  42.  
  43. time(&start);
  44. is_prime(num2);
  45. time(&end);
  46. cout<<difftime(end,start)<<"\n";
  47.  
  48. time(&start);
  49. is_prime(num3);
  50. time(&end);
  51. cout<<difftime(end,start)<<"\n";
  52.  
  53. time(&start);
  54. is_prime(num4);
  55. time(&end);
  56. cout<<difftime(end,start)<<"\n";
  57.  
  58. time(&start);
  59. is_prime(num5);
  60. time(&end);
  61. cout<<difftime(end,start)<<"\n";
  62.  
  63. //10,000,000,000,000th prime is 29,996,224,275,833
  64. //time(&start);
  65. //is_prime(num6);
  66. //time(&end);
  67. //cout<<difftime(end,start)<<"\n";
  68.  
  69.  
  70.  
  71. return 0;
  72. }

 

YES
0
YES
0
YES
1
YES
11
YES
121
 

 

این خروجی سیستم منه، تازه آخریه رو هم کامنت کردم اگه حواستون به کد بوده باشه ، البته ممکنه سیستم شما خیلی شاخ تر باشه و تو زمان های بهتری به جواب برسید (با همین کد) ولی نکته ای  که هست اینه که تو دنیای واقعی که اینا اصن عدد نیستن خیلی کوچیکن مخصوصاً وقتی مباحثی مثل رمزنگاری مطرح میشه تازه می فهمید این عددا خیلی خیلی کوچولو اند و این زمان اجرا اصن مناسب حالشون نیست :دی

خب پس بریم دنبال یه کم سرعت بیشتر

یه ادعای بزرگ و خوب : ادعا می کنیم اگر عدد طبیعی mاول نباشد آنگاه عاملی کوچکتر مساوی رادیکال m خواهد داشت

اثبات ساده است چون m اول نیست پس مرکبه یعنی حداقل میشه اون رو به صورت ضرب دو تا عامل کوچکتر از خودش نوشت یعنی

m=pq

ادعامون اینه که یکی از این عامل ها باید  کوچکتر مساوی رادیکال m باشه یعنی

 

این عبارت میگه اگر m اول نباشد آنگاه عاملی مانند p وجود دارد که m را عاد می کند و  کوچکتر مساوی رادیکال m است

خب فرض کنیم که این حرف درست نباشه می دونیم که m مرکبه پس میشه نوشت

m=pq

چون فرض کردیم که حرف قبلیمون درست نیست پس هم p و هم q باید از رادیکال m بزرگتر باشن یعنی

 

ولی این یعنی

 

و این یعنی چرت محض :دی ، و این چرت بودن به این دلیله که فرض کردیم m که مرکبه هیچ عامل کوچکتر مساوی رادیکال m نداره و این فرضه غلط بود

خب حالا که اینو می دونیم چی کار می تونیم بکنیم؟

بله درست فهمیدین (الکی) اگه قرار باشه یه عددی اول نباشه باید یه عدد کوچکتر  مساوی رادیکالش وجود داشته باشه که اونو عاد کنه

پس می تونیم کد قبلیمون رو به صورت زیر باز نویسی کنیم

 

  1. #include <iostream>
  2. #include <time.h>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. typedef unsigned long long Int64;
  7.  
  8. void is_prime(Int64 num){
  9.  
  10. bool prime=true;
  11.  
  12. if(num==1){
  13. prime=false;
  14. }
  15.  
  16. Int64 sq=sqrt(num);
  17. for(Int64 i=2;i<=sq;i++){
  18. if(num%i==0){
  19. prime=false;
  20. break;
  21. }
  22.  
  23. }
  24.  
  25. if(prime){
  26. cout<<"YES\n";
  27. }else{
  28. cout<<"NO\n";
  29. }
  30.  
  31. }
  32. /*********/
  33. int main(){
  34.  
  35. time_t start,end;
  36.  
  37. Int64 num1=13,num2=1069,num3=29005541,num4=334214459,
  38. num5=3780008329,num6=29996224275833;
  39.  
  40. time(&start);
  41. is_prime(num1);
  42. time(&end);
  43. cout<<difftime(end,start)<<"\n";
  44.  
  45. time(&start);
  46. is_prime(num2);
  47. time(&end);
  48. cout<<difftime(end,start)<<"\n";
  49.  
  50. time(&start);
  51. is_prime(num3);
  52. time(&end);
  53. cout<<difftime(end,start)<<"\n";
  54.  
  55. time(&start);
  56. is_prime(num4);
  57. time(&end);
  58. cout<<difftime(end,start)<<"\n";
  59.  
  60. time(&start);
  61. is_prime(num5);
  62. time(&end);
  63. cout<<difftime(end,start)<<"\n";
  64.  
  65. //10,000,000,000,000th prime is 29,996,224,275,833
  66. time(&start);
  67. is_prime(num6);
  68. time(&end);
  69. cout<<difftime(end,start)<<"\n";
  70.  
  71.  
  72.  
  73. return 0;
  74. }

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

YES
0
YES
0
YES
0
YES
0
YES
0
YES
1
 

می بینید که داره مثل سگ کار می کنه ولی خب هنوز اون آخریه یه ثانیه است و این خیلی خوب نیست

می تونید رادیکال m رو هم حساب نکنید و کد رو به صورت زیر بنویسید

 

  1. void is_prime(Int64 num){
  2.  
  3. bool prime=true;
  4.  
  5. if(num==1){
  6. prime=false;
  7. }
  8.  
  9. for(Int64 i=2;i*i<=num;i++){
  10. if(num%i==0){
  11. prime=false;
  12. break;
  13. }
  14.  
  15. }
  16.  
  17. if(prime){
  18. cout<<"YES\n";
  19. }else{
  20. cout<<"NO\n";
  21. }
  22.  
  23. }

که این خیلی فرق نداره با قبلی از لحاظ سرعت

ولی  یه نکته خیلی ساده که تو کد بالا بهش دقت نشد اینه که وقتی عددی به دو بخش پذیر نبود می ریم بخش پذیری به سه رو چک می کنیم یعنی i یه دونه افزایش پیدا می کنه توی حلقه for و بعد وقتی به سه بخش پذیر نبود میریم بخش پذیری به چهار رو امتحان می کنیم و بعد پنج و بعد شیش و بعد هفت و بعد هشت

ولی خب یه جای کار می لنگه ، می لنگه از این لحاظ که داریم کار اضافی انجام میدیم و اون اینکه وقتی یه عددی به دو بخش پذیر نباشه خب دیگه به هیچ عدد زوج دیگه ای هم بخش پذیر نخواهد بود پس نیازی نیست بخش پذیری به اعداد زوج رو چک کنیم در نتیجه می تونیم کد رو به صورت زیر باز نویسی کنیم

 

 

  1. void is_prime(Int64 num){
  2.  
  3. bool prime=true;
  4.  
  5. if(num==1){
  6. prime=false;
  7. }
  8.  
  9. if(num>2 && num%2==0){
  10. prime=false;
  11. }
  12.  
  13. Int64 sq=sqrt(num);
  14. for(Int64 i=3;i<=sq;i+=2){
  15. if(num%i==0){
  16. prime=false;
  17. break;
  18. }
  19.  
  20. }
  21.  
  22. if(prime){
  23. cout<<"YES\n";
  24. }else{
  25. cout<<"NO\n";
  26. }
  27.  
  28. }

می بینید که توی این کد جدید بررسی تقسیم پذیری به دو رو آوردم خارج حلقه و توی حلقه فقط تقسیم پذیری به اعداد فرد رو دارم چک می کنم اینجوری کدمون سرعتش تقریباً باید دو برابر بشه

 

خب ما هنوز اول راهیم و کلی با این اعداد اول کار داریم که بعداً پست های بیشتری در موردش می زارم

فعلاً تا اینجا کافیه

فقط یه نکته برای خیلی ریز بینا یا اونایی که چیزای بیشتری در مورد پیچیدگی می دونن و اون اینکه اون تحیلی پیچیدگی که اول کار واسه اون الگوریتم ساده هه آوردم خیلی درست نیست یعنی درسته که تعداد مراحل اجرای دستورات داخل حلقه رابطه مستقیم داره با N ولی نوشتن پیچیدگی به صورت O(N)d خیلی درست نیست یا مثلاً برای الگوریتم دوم درسته که تعداد اجرای دستورات به رادیکال N وابسته است ولی خیلی درست نیست که بگیم مرتبه اجرایی برنامه O(sqrt(N))d هست هر چند برای کار های فعلی ما همین قدر کافیه که بدونیم تعداد دفعات اجرای فلان دستورات چه رابطه ای با N داره ولی بحث جامع تری میشه در مورد پیچدیدگی ها کرد که شما رو برای شروع ارجاع می دم به کتاب زیر

Foundations of Algorithms Using C++ Pseudocode

Richard Neapolitan and Kumarss Naimipour

 

 

فصل مربوط به پیچدگی ها یعنی فصل زیر

Computational Complexity and Interactability—An Introduction to the Theory of NP

 

اونجا یه قسمت در مورد اندازه ورودی مسئله بحث می کنه که جالبه حتماً بخونید با این عنوان

Input Size Revisited

 

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