درخواست الگوریتم ( الگوریتمی بنویسید که بزرگترین عدد 4رقمی اول را چاپ کند )

[maziarb]

سلام سوال من این هستش:

الگوریتمی بنویسید که بزرگترین عدد 4رقمی اول را چاپ کند

ممنون

[maziarb]

سلام من فقط 8ساعت دیگه وقت دارم

[Life24]

داداش چی شد؟
اگر پیدا کردی بزار تو سایت
منم فکر کردم نرسیدم جایی

[IP007]

باید مثلا از 1000 تا 9999 رو بشماره
هر باز جذر عدد رو بگیره و چک کنه که اعداد قبلش به اون جذر تقسیم پذیرن یا نه

[Life24]

باید مثلا از 1000 تا 9999 رو بشماره
هر باز جذر عدد رو بگیره و چک کنه که اعداد قبلش به اون جذر تقسیم پذیرن یا نه

داداش قسمت دوم رو بازش نمیکنی یکمی

[IP007]

منبع :

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

الگوريتم پيدا کردن اعداد اول
اين اول هست، اون نيست!

اين هفته مي‌خواهيم برنامه‌اي ساده‌اي بنويسيم که تشخيص دهد عدد ورودي عدد اول هست يا خير؟ سپس در يک بازه اعداد اول را جستجو کنيم. نخست بايد عدد اول را تعريف کنيم: عدد اول عددي است که تنها بر خودش و بر 1 بخش‌پذير باشد.براي تشخيص عدد اول بودن کافيست عدد را در يک حلقه Nتايي بياندازيم (N برابر خود عدد است) که از 2 شروع مي‌شود و در اين حلقه عدد N را بر I (انديس حلقه) تقسيم مي‌کنيم، اگر خارج قسمت صفر شد عدد اول نيست و اگر حاصل هيچ وقت صفر نشد يعني عدد اول است که کد آن به‌صورت زير است:

}(public static bool isPrime(int args

for (int i = 2; i « args; i++){

if (args % i == 0) return false;}

return true;

{

خب اين سه خط جواب مي‌دهد و درست است، اما تنها براي اعداد کوچک. فرض کنيد عدد ورودي 2147483647 باشد، براي چک کردن اول بودن اين عدد زماني معادل با 11ثانيه بايد صرف شود که اين زمان زيادي است. يک مقدار الگوريتم را بهتر مي‌کنيم تا اين زمان کاهش پيدا کند، بگذاريد يک مقداري اعداد اول را در رياضي بررسي کنيم. عدد 2 تنها عدد اول زوج است، پس اگر عدد ورودي 2 بود، اول است و ديگر هيچ عدد اول زوجي وجود ندارد. پس ما اعداد زوج را هم حساب نمي‌کنيم و اگر عدد ورودي بر 2 بخش‌پذير بود نيز تابع با نتيجه false به‌کار خودش خاتمه مي‌دهد. خب، با اين کار ما نصف اعداد 2 تا عدد ورودي x را بررسي نمي‌کنيم و فقط اعداد فرد را بررسي مي‌کنيم، که کد آن به‌صورت زير است:

public static bool isPrime(int args){

if (args == 2) return true;

else if (args % 2 == 0) return false;

for (int i = 3; i « args; i = i + 2 ){

if (args % i == 0) return false;}

return true;

}

بسيار خوب، بار ديگر اين کد را با عددي که در بالا ذکر شد تست مي‌کنيم. نتيجه اين است که کد جديد 5ثانيه طول مي‌کشد يعني از نصف هم کمتر. پس ما به الگوريتم به ‌نسبت بهتري رسيديم. ولي بگذاريد يک مقداري بيشتر کد را بررسي کنيم و اين زمان را کمتر کنيم.
براي اينکه الگوريتم را کمي بهتر کنيم‌، فرض کنيد A*B=C است. براي اينکه A+B بيشترين مقدار را داشته ‌باشند، بايد A=B باشد (به اين خاطر بررسي مي‌کنيم که مجموع دو عدد A و B بيشترين مقدار را داشته ‌باشد که بازه‌ لازم براي تشخيص عدد اول بزرگتر شود تا نتيجه با دقت بيشتري به‌دست آيد)، يعني A به توان2 برابر C باشد در نتيجه (A=B=Sqrt(C است.
در نتيجه اگر C عددي اول نباشد قطعا يک ريشه کوچکتر مساوي عدد(Sqrt(C خواهد داشت (اگر C يک ريشه بزرگتر از جذر خودش داشته ‌باشد ريشه ديگر قطعا کوچکتر از جذر C خواهد بود). در نتيجه اگر بين عدد 3 و جذر عدد ورودي يک عدد غيراول وجود داشته ‌باشد، در نتيجه عدد ورودي اول نيست، در غير اين‌صورت عدد ورودي اول است.
الگوريتم ما با اين روش خيلي بهتر از قبل شد. اگر در روش قبل نصف اعداد بررسي مي‌شدند، در اين روش اعداد فرد بين 3 و جذر يک عدد مورد بررسي قرار مي‌گيرند و از آنجا که درجه رشد مجذور کمتر از نصف عدد است، مثلا اگر عدد ورودي برابر 9 باشد نصف آن برابر 5/4 و جذر آن برابر 3 است و در عددي مثل 64 اختلاف بين جذر و نصف عدد برابر 22 است و در اعداد بزرگتر اين اختلاف بيشتر مي‌شود، بنابراين جستجو بين اعداد فرد بين 3 و جذر يک عدد و اعداد فرد موجود بين آنها هزينه کمتر و بازدهي بيشتري دارد.
حال الگوريتم را طبق توضيحات گفته شده بازنويسي مي‌کنيم:

public static bool isPrime(int args){

double sqrtN = Math.Sqrt(args);

if (args == 2) return true;

else if (args % 2 == 0) return false;

for (int i = 3; i «= sqrtN; i = i + 2){

if (args % i == 0) return false;}

return true;

}

اين الگوريتم براي عدد 2147483647 چيزي در حدود ?هزارم ميلي‌ثانيه طول مي‌کشد، يعني حتي به يك ميلي‌ثانيه هم نمي‌رسد. خب الان به يک الگوريتم بهينه براي پيدا کردن عدد اول رسيديم. حال بخش دوم مساله، پيدا کردن تعداد اعداد اول موجود در يک بازه است. براي اين مساله نياز به الگوريتم جستجوي مناسب داريم که داده‌ها را با استفاده از تابع isPrime ----- کنيم و به‌صورت بهينه، تمامي اعداد اول موجود در يک بازه را به‌دست بياوريم.

امير بهاءالدين سبط الشيخ

[IP007]

نمیدونم چرا درست عمل نمیکنه
به جای، جذر، از نصف کردن استفاده کن،
i رو هم یکی یکی برو بالا

[IP007]

فهمیدم مشکلش چیه! اصلا نباید به این روزنامه جام جم اعتماد کرد

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

[Life24]

بزرگوارفلوچارتش میخوام (یا لگوریتم)
البته برنامه اش هم خدا خواست لازم داشتیم جور شد با هم

[IP007]

من الگوریتم، فلوچارت حالیم نیست، یعنی میخوای یه عکس بکشم؟! الگوریتم رو از رو کد بنویس دیگه