اعداد اول

[داش آکــُـل]

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

[tdkhakpur]

عزيزم براي اين كار يك ميليون دلار جايزه گذاشتن كه رياضي دانها پيداش كنند اگر پيدا كردم به خاطر شيريني كار يك دلار از يك ميليون دلار رو بهت هديه ميكنم.:لبخندساده:
ولي اگر كد براي اينكار بخواهيد چيزي نيست.


int n=23;
bool Find=false;
for( int i=2; i<n/2 && !Find; i++ )
if( n%i == 0 ) Find = true;
if( Find )
ShowMessage("add aval nist");
else
ShowMessage("add aval ast");

[kitten]

دوست عزیز فرمول خواستی برای این کار نیست اما باید برای این کار الگوریتمش را بنویسی که باید اعداد تا n تقسیم بر 2 چک کنی (که خودش می شه یه حلقه) و ........

[بانوی ایران]

اگر منظورتون عامل های اوله عدده
دوتا حلقه تو در تو بذارید که حلقه داخلی متغیرfactorرو مقدار اولیه 2 بدید بهش و هر چی عامل 2 داره میکشه بیرون و حلقه بزگ به factor یکی اضافه میکنه و تا زمانی که factor <n/2 باشه ادامه میده و وارد حلقه کوچکتر میشه

[mortezamsp]

لازم نیست تا 2/n همه بررسی بشن. برای سریع تر شدن کار میشه با تغییراتی فقط تا رادیکل n رو بررسی کرد.



for( int i=2; i<n/2 && !Find; i++ )

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

[tdkhakpur]

اگه میخوای از این هم سریعتر بشه باید مقدار √n رو بیرون از حلقه چاپ کنی و داخل حلقه فقط اون عدد رو بذاری.وگرنه برای اعداد خیلی بزرگ باید سالها منتظر جواب بمونی.
مام همین کار رو کردیم که تو acm ازمون ایراد گرفتن.
اين فقط مثال بود و الا هر چند سريعتر هم باشد فايده اي ندارد بالخره عدد n تا دنيا دنياست وجود دارد و هميشه احتياج به سرعت..!

[Salar Ashgi]

یک الگوریتم نسبتا بهینه : تمام اعداد اول بجز 2 ، فردند ! پس ما در حلقه لازم نیست

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

بخشپذیر بشه ، اینطوری تقریبا نصفی از داده ها یا بیشتر ، از مقایسه حذف میشوند و

الگوریتم بهینه تر میشود :



bool is_prime(int n){
bool res = true;
if(n<=1)
res = false;
if(n==2)
res = true;
if(n%2==0 && n!=2)
res = false;
else{
for(int i=3;i<=sqrt(n);i+=2){
if(n%i==0){
res = false;
break;
}
}
}
return res;
}

[#Elahe#]

من هم لینو واسه کوچکتر از 100 نوشتم که تا جذر حساب میکنه !!


#include<iostream.h>
#include<math.h>
#include<conio.h>
int main()
{
clrscr();

int i=2,j=2,k=2,x;

while (i<=100)
{
while (k<=sqrt(i))
{
if (i%k==0)
j=j+1;
k++;
}
if (j==2)
cout<<i<<"\n\n";
k=2;
i++;
j=2;
}
cin>>x;
return 0;
}