PDA

View Full Version : سوال: برنامه ای برای تعیین عدد اول



tree23
دوشنبه 28 مرداد 1387, 10:34 صبح
سلام
ببخشید که من اینقدر مبتدیم.
یه برنامه برای عدد اول نوشتم که عدد رو بگیره و مشخص کنه اوله یا نه!اما یه ایراد کوچیک تو انتخاب نوع حلقه و نحوه استفادش دارم.ممنون میشم یکی راهنماییم کنه!اگه سوال نا مفهومه بگید تا بزودی سورسش رو هم بفرستم.

s.mostafa.rahmani
دوشنبه 28 مرداد 1387, 10:39 صبح
خوب سورسشو بفرستيد حتماً بهتره!!

mehdad.koulab
دوشنبه 28 مرداد 1387, 17:42 عصر
اگه سورسشو بذارين كه عاليه
ولي اگه الگوريتم رو بخواين شما بايد عدد رو نصف كنين و بعد شروع به تقسيم كنين تا به 1 برسين و ... ولي اينم بگم من اينو بلدم شايد روشهاي بهينه تري هم باشه.

MOHSEN8000
دوشنبه 28 مرداد 1387, 20:00 عصر
می تونید از این کد استفاده کنید.



for ( i = 2; i <= sqrt (n) ; i++ ) {
if (( n % i ) == 0 ){
break;
}
}


و حالا بعد از پایان حلقه چک کنید که مقدار i چقدر است. اگه مقدار i برابر بود با رادیکال n به اضافه یک ، معلومه که حلقه تا پایان اجرا شده. پس یعنی این عدد اول هست ( چون مقسوم علیه کمتر از رادیکال n ندارد ) و اگه مقدار i این نبود ، یعنی باقیمانده n بر i شده 0 که از حلقه خارج شده و بنابراین عدد اول نیست.

++Hichkas
دوشنبه 28 مرداد 1387, 23:26 عصر
می تونید از این کد استفاده کنید.



for ( i = 2; i <= sqrt (n) ; i++ ) {
if (( n % i ) == 0 ){
break;
}
}


و حالا بعد از پایان حلقه چک کنید که مقدار i چقدر است. اگه مقدار i برابر بود با رادیکال n به اضافه یک ، معلومه که حلقه تا پایان اجرا شده. پس یعنی این عدد اول هست ( چون مقسوم علیه کمتر از رادیکال n ندارد ) و اگه مقدار i این نبود ، یعنی باقیمانده n بر i شده 0 که از حلقه خارج شده و بنابراین عدد اول نیست.
برای اینکار می تونی به صورت زیر عمل کنی :
()int main
log n }
" cout <<" enter a positive integer
;cin>>n
eif (n< 2) cout << n << " is not prime ";
;"else if (n<4 ) cout <<n<< " is prime
else if ( n% 2 == 0 ) cout << n << = 2 "
else
(for ( int d=3 ; d<=n/2 ; d+=1 }
if (n%d==0)
{ cout << n<< " = " << d << n/ d << endl ;
exsit (0)
}
cout << n << " is prime " .
;{
{

MOHSEN8000
سه شنبه 29 مرداد 1387, 00:08 صبح
برای اینکار می تونی به صورت زیر عمل کنی :
()int main
log n }
" cout <<" enter a positive integer
;cin>>n
eif (n< 2) cout << n << " is not prime ";
;"else if (n<4 ) cout <<n<< " is prime
else if ( n% 2 == 0 ) cout << n << = 2 "
else
(for ( int d=3 ; d<=n/2 ; d+=1 }
if (n%d==0)
{ cout << n<< " = " << d << n/ d << endl ;
exsit (0)
}
cout << n << " is prime " .
;{
{


نیازی نیست تا n/2 چک کنی. تا رادیکال n که چک کنیم کافیه

Salar Ashgi
سه شنبه 29 مرداد 1387, 00:41 صبح
کدی بهینه تر و بهتر :

تابعی برای تشخیص اول بودن :


#include <iostream>
#include <conio>
#include <math>
int Prime(int n){
int k=0;
if(n<=1)
return -1;
else{
for(int i=2;i<=sqrt(n);(i%2==0 ? i++ : i+=2)){
if(n%i==0)
k++;
}
return k;
}
}
============================
در این تابع اگر ورودی اول باشد ، خروجی صفر است ، در غیر اینصورت خروجی غیر صفر

است
============================
توضیحات : عدد اول ، عددی است بر هیچ یک از مقسوم علیه های اول کوچکتر از خود

بخشپذیر نباشد (کوچکتر از جذر عدد درست تر است) ، با توجه به این تعریف ما حد بالای

حلقه را تا جذر n قرار داده ایم ، و در تابع برای تشخیص عدد اول اگر عددی در این بازه بین

2 تا جذر n یک مقسوم علیه n باشد ، آن عدد دیگر اول نیست ولی ما در مقایسه ها لازم

نیست همه اعداد از 2 تا جذر n را بررسی کنیم بلکه فقط اعداد فرد را بررسی کرده و اعداد

زوج را از محاسبه خود بیرون می اندازیم ، چون می دانیم تنها عدد زوج و اول 2 است و بقیه

اعداد زوج ، اول نیستند !!! و این کار در زمان محاسبات و مرتبه زمانی الگوریتم تاثیر خوبی

دارد !!!! امیدوارم مطلبم مفید بوده باشد !!!! موفق باشید !!!!:لبخندساده:

bsng110
چهارشنبه 30 مرداد 1387, 21:43 عصر
هوالحکیم سلام ببخشید مزاحم می شم. هر دو کد خوب بودن ولی هر دوشون یک عیب کوچیک داشتن. کدی که از n/2 استفاده می کرد، توسط کامپایلر بهینه می شود ولی کدی که از (sqrt(n استفاده می کرد، حتی توسط کامپایلر هم بهینه نمی شود! قضیه چیست؟ ببینید در شرط حلفه، هر مرتبه که شرط بررسی می شود، عبارت داخل شرط محاسبه می شود اما آیا به نظر شما نیاز است که تابع جذر گیری با آن همه پیچیدگی را چندین بار صدا بزنیم؟ پس بهتر است جذر را در یک متغیر ریخته و سپس متغیر را در شرط بگذاریم اما کدی که n/2 داشت نیز همین عیب را داشت، ولی آن کد را کامپایلر می توانست بهینه کند چرا که تابعی را فراخوانی نمی کرد و کامپایلر می توانست به صورت قطعی در مورد ان تصمیم بگیرد و آن را بهینه کند یعنی یک بار ان را محاسبه کرده و دفعه های بعدی از همان مقدار محاسبه شده استفاده کند. باز هم شرمنده که وسط بحثتون پریدم. یا علی خدانگهدارتون