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

[maziarb]

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

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

ممنون

[maziarb]

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

[Life24]

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

[IP007]

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

[Life24]

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

[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]

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

[alireza1411]

الگوریتم کد برنامه اینه:
باید شروع کنی از 9999 بیای عقب تا به اولین عدد برسی اون بزرگترین عدد اوله.
یهn تعریف کن و اون رو در ابتدا برابر با 9999 بزار بعد در هر مرحله این کارارو کن:
در یک حلقه ی for متغییر i رو که وقدار اولیش یکه ، یکی یکی زیاد کن و مدام n رو بر اون تقسیم کن تا به رادیکال n برسی . اگه به هیچ کدو م از اعداد نخورد n اول است در غیر این صورت n رو یکی کم کن.
این الگوریتمشه کدش رو هم میخوای به زبون سی پلاس پلاس برات بنویسم؟

[alireza1411]

اگر بازم کدش رو خواستید، بگید براتون بنویسم به زبون سی یا سی پلاس پلاس. به یه موضوع دقت کنید که باید تا رادیکال n پیش برید دلیلش هم اینه:
اگه تا رادیکال، عددی پیدا شد که هیچ، عددn اول نیست .در غیر این صورت دیگر عددی پیدا نمیشود چون اگر عددی مانند f بزگتر از رادیکالn باشدکهn بر ان بخش پذیر باشد پس f باید در عددی کوچکتر ازرادیکالn ضرب شود تا n بدست اید که چنین عددی که از رادیکال n کوچکتر باشد یافت نشد.حله؟
اون موقعی که ما تا نصف عدد پیش میریم برای شمردن مقسوم علیه ها استفاده میشه.

[IP007]

فقط بگم، تا رادیکال پیش بری ، جواب درست نمیده، مثلا 19 و 20، جذرشون دو دهم فرق داره، و هر دوشون رو میگه اول نیست،
پس باید جزر عدد رو ازش،سقف بگیری، یعنی متضاد جزء صحیح

[alireza1411]

به بالایی:
اشتباه نکن. طبق دلایلی که تو بالا اوردم اگه تا براکت(خود براکت رو هم حساب کن) جذر عدد بریم درست میشه چون اگه عددی بیشتر از براکت جذرش باشه باید در عددی کوچکتر از براکت جذرش ضرب شود تا خود عدد بدست بیاد.حله؟
در ضمن من نفهمیدم شما چجوری به نتیجه رسیدین که 19 اول نیست.
؟؟؟!!!!
چون اگه 19 رو بر اعداد 2 و 3 و 4 تقسیم کنیم چون به هیچ کدوم نمیخوره.پس اوله .الا شما چی کار کردین من خبر ندارم.
استاد ما تو ترم یک این برنامرو به ماد اده بودکه:
اعداد اول کوچکتر از n رو چاپ کنید با این روش که برای تشخیص هر عدد اول دیگر ان عدد را بر کل اعداد تا رادیکالش تقسیم نکنید و بر اعداد اول کوچکتر از را دیکالش تقسی م کنید یعنی برا ی تشخیص اینکه مثلا 71اول است یا نه ان را فقط بر اعداد2و3و5و 7
تقسیم کنیم.
حالا کی مرده کد این برنامه دومیرو بزاره؟؟؟؟؟
هر کی بتونه یه لپ لپ جایزه داره!!!:31:

[IP007]

به بالایی :
عزیزم، برنامه اون نتیجه رو میده،
19 و 20 هر دو جذرشون 4 و خورده ای هست، براکت بگیری که دیگه افتضاح میشه
یکم برو جزوه ریاضیتو بخون :دی

[alireza1411]

به بالایی:
مثل اینکه اصلا نخوندی چی گفتم.یه بار با دقت بخون که چرا برای تشخیص اینکه یه عدد اول هست یا نیست ، تا جذرش پیش میریم مفهوم این رو دقیق متوجه شی. این که چرا تا براکت میری مسجل میشه.
در ضمن من نفهمیدم برنامه ای که نوشتی میگی 19 اول نیست؟؟؟!!!حالا خوبه منم بگم جزوه ی ریاضیتو بخون!!!:21:

[IP007]

برنامه ی منو اجرا کن، مشکلی توش نمیبینی