اعداد اول

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

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

 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");

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

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

نقل قول:

---

نوشته شده توسط CppBuilder2006

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

---

نقل قول:

---

نوشته شده توسط tdkhakpur

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

---

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

نقل قول:

---

نوشته شده توسط mortezamsp

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

---

اين فقط مثال بود و الا هر چند سريعتر هم باشد فايده اي ندارد بالخره عدد n تا دنيا دنياست وجود دارد و هميشه احتياج به سرعت..!

یک الگوریتم نسبتا بهینه : تمام اعداد اول بجز 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;

}

من هم لینو واسه کوچکتر از 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;

}