اشکال در برنامه تعیین عدد اول

[محسن=0]

سلام.
برنامه زیر یه عدد رو میگیره مشخص میکنه اول هست یا نه . مشکل اینه که اگه اول نباشه اول نیست رو مرتب تکرار میکنه .
اشکالش چیه ؟
ایا به غیر از اون مشکل دیگه داره یا نه . خوب نوشته شده یا نه ؟
متشکر

#include <iostream>

using namespace std;

int main()

{

                long long n;

                cout << "yek adad vared konid :";

                cin >> n;





                int i = 2 ;

                while ( i < n )

                {

                                if ( n%i == 0)

                                                cout << n <<"avval nist ";



                                else

                                i++;

                }

                cout << "avval ast";

                return 0;

}

[samin_panahi]

سلام
خوب شما اومدید توی حلقه cout گذاشتید
یه bool تعریف کنید بعد از if اون رو false کنید و از حلقه خارج شید
بیرون حلقه هم یه if بذارید و بررسی کنید اگر اون bool مقدارش true بود بگه اول هست اگه نبود بگه اول نیست

[epc1380]

همچنین بهتره یه break بین خط 14 و 15 بذاری که الکی تقسیم نکنه.برای بهینه سازی بیشتر هم میتونی بنویسی ((while(i<=sqrt(n).چون رفتن تا جذر عدد کافیه.(البته باید برای این کار دستور<include<cmath# رو به ابتدای برنامه اضافه کنی.

[ehsan_faal]

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

[zero_ox]

سلام.
برنامه زیر یه عدد رو میگیره مشخص میکنه اول هست یا نه . مشکل اینه که اگه اول نباشه اول نیست رو مرتب تکرار میکنه .
اشکالش چیه ؟
ایا به غیر از اون مشکل دیگه داره یا نه . خوب نوشته شده یا نه ؟
متشکر

#include <iostream>

using namespace std;

int main()

{

                long long n;

                cout << "yek adad vared konid :";

                cin >> n;





                int i = 2 ;

                while ( i < n )

                {

                                if ( n%i == 0)

                                                cout << n <<"avval nist ";



                                else

                                i++;

                }

                cout << "avval ast";

                return 0;

}

اشکالاتش که دوستان گفتن . فقط من کدخودت رو با کمی تغییذ می ذارم تا بتونی نتیچه تقیسم ها رو هم ببینی و استفاده از جذر فقط تعداد تقیسم ها رو کاهش می ده . که می تونی امتحان کنی

#include <iostream>

#include <cmath>// for sqrt();

using namespace std;

int main()

{

 long long n;

 bool c=true;

 cout << "yek adad vared konid :";

 cin >> n;

 int i = 2 ;

while ( i<n)//inja mitoni ta (i<=sqrt(n))

{

 if ( n%i == 0)

c=false;

cout << n <<" % "<<i<<"=  "<<n%i<<"\n";

i++;

}

if(c==true)

cout<<endl<<n<<" adad aval hast\n";

else

cout<<endl<<n<<" adad aval nist\n " ;

return 0;

}

[amirtork]

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

سلام.
در واقع، اگر صحبت در مورد بهینه سازی باشه، بهتره که به هیچ عنوان! از تابع sqrt استفاده نشه. این تابع تابع خیلی زمان بری هست! و اگر شما اون رو داخل یک حلقه استفاده کنید، در contest های ACM به راحتی time-limit میخورید.
بهتر این هست که برای مقایسه i به توان دو رو در نظر بگیریم. به این صورت که : ((while(i*i <=n با این کار علاوه بر اینکه از هزینه ی زمانی فراخوانی توابع( به خصوص جذر که خیلی زمان بر هست) جلوگیری میشه. از هزینه های جانبی خود sqrt هم جلوگیری میشه.

[golbafan]

من هم در مورد بهینه سازی برای اعداد اول یک چیزی اضافه کنم:

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

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

مثلا برای اینکه بفهمیم 100 اول هست یانه:

جذر 100 میشه 10

اعداد اول قبل از 10 : 2 و 3 و 5 و 7

تعداد تقسیم ها = 4

حالا توی این مورد میبینیم بر 2 تقسیم میشه و عملیات رو پایان میدیم

[محسن=0]

سلام. ممنون از همتون .متشکر
من از دو تا حلقه while و دستور break استفاده کردم. و میخوام فقط از همین ها استفاده کنم.
برنامه به نظر درست میاد اما برای اعداد خیلی بزرگ مقدار زباله تحویل میده.مثل :100000000000000000000
ایا برنامه مشکلی داره یا اعداد رو با نوع متغیر دیگه وارد کنم؟

#include <iostream>

using namespace std;

int main()

{

                long long n;

                int i =2 ;

                cout <<"lotfan yek adad vard konid :" ;

                cin >> n;

                if ( n == 1 )

                                cout << n << " avval nist ";

                if ( n == 2 )

                                cout << n << " avval ast ";



                while (i < n)

                {

                                   if ( n%i == 0 )

                                                cout << n << " avval nist .";

                                                break ;

                                   i++;

                }

                while (i < n)

                {

                                   if ( n%i  != 0 )

                                                cout << n << " avval ast .";

                                                break ;

                                   i++;

                }

                return 0 ;

}

[amirtork]

سلام.
مشکلی که کد شما داره این هست که شما قصد دارید دوبار یک حلقه رو تکرار کنید، در صورتی که حلقه ی دوم تکرار نمیشه، چون شرط خروج از حلقه ی اول طوری هست که i = n هست موقع خروج. و شرط ورود به حلقه ی دوم کوچکتر بودن i از n هست.
در واقع لزومی هم به اجرای حلقه ی دوم نیست! اگر در حلقه ی اول به پیام aval nist برنخوردیم. پس عدد اول هست! لازم نیست دوباره چک کنیم که اول هست یا نه.
مورد دوم هم این هست که، خواهشا به صحبت هایی که در بالا شد دقت کنید! دوستان راه کار هایی رو برای افزایش سرعت برنامه تون ارایه دادن ولی همچنان شما از هیچ کدوم بهره نبردید.
و مورد سوم : شاید عددی که وارد کردید از محدوده ی long long خارج باشه! و البته این سوال برام پیش اومده که تعیین اول بودن یا نبودن همچین عددی در چه برنامه ای میتونه کاربرد داشته باشه!
در آخر، اگر شما نیاز به تابعی برای تعیین عدد اول دارید، و قصدتون این هست که برسی اعداد اول رو در بازه ای مشخص انجام بدید، پیشنهاد میکنم از الگوریتم غربال اراتوستن استفاده کنید و اعداد اول رو تا جایی که لازم دارید در vector ذخیره کنید، تا از مدت زمان مورد نیاز برای تعیین اول بودن یا نبودن عدد کم کنید.

[محسن=0]

سلام.
مشکلی که کد شما داره این هست که شما قصد دارید دوبار یک حلقه رو تکرار کنید، در صورتی که حلقه ی دوم تکرار نمیشه، چون شرط خروج از حلقه ی اول طوری هست که i = n هست موقع خروج. و شرط ورود به حلقه ی دوم کوچکتر بودن i از n هست.
در واقع لزومی هم به اجرای حلقه ی دوم نیست! اگر در حلقه ی اول به پیام aval nist برنخوردیم. پس عدد اول هست! لازم نیست دوباره چک کنیم که اول هست یا نه.
مورد دوم هم این هست که، خواهشا به صحبت هایی که در بالا شد دقت کنید! دوستان راه کار هایی رو برای افزایش سرعت برنامه تون ارایه دادن ولی همچنان شما از هیچ کدوم بهره نبردید.
و مورد سوم : شاید عددی که وارد کردید از محدوده ی long long خارج باشه! و البته این سوال برام پیش اومده که تعیین اول بودن یا نبودن همچین عددی در چه برنامه ای میتونه کاربرد داشته باشه!
در آخر، اگر شما نیاز به تابعی برای تعیین عدد اول دارید، و قصدتون این هست که برسی اعداد اول رو در بازه ای مشخص انجام بدید، پیشنهاد میکنم از الگوریتم غربال اراتوستن استفاده کنید و اعداد اول رو تا جایی که لازم دارید در vector ذخیره کنید، تا از مدت زمان مورد نیاز برای تعیین اول بودن یا نبودن عدد کم کنید.

سلام
متشکر از شما بابت تذکراتی که دادین.من قصدم این هست که از تمام را های ممکن برای نوشتن یه برنامه استفاده کنم . و فقط محدود به یه راه نشم.
در باره محدوده long long هم کلا برام جذاب هست بدونم بعد از این نوع به انواع بزرگتری هم میرسیم یا نه؟

الگوریتم غربال اراتوستن و

vector هم هنی نرسیدم که بخونم

[amirtork]

سلام.
برای استفاده از اعدادی بزرگتر از محدوده ی اعداد استاندارد در C++‎، میتونید خودتون این نوع رو ایجاد کنید، با استفاده از آرایه ها، لیست پیوندی و ... .
البته فکر میکنم در سطح اینترنت هم اگر جست و جو کنید بتونید کلاس های آماده ای رو پیدا کنید برای انجام این کار. من کلمات کلیدی BigNum و یا BigInt رو برای جست و جو پیشنهاد میکنم.

[ehsan_faal]

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

The GNU Multiple Precision Arithmetic Library