PDA

View Full Version : پیدا کردن اعداد اول



Amir 2010a
یک شنبه 14 دی 1393, 20:22 عصر
سلام
دوستان عزیز کسی برنامه ای به زبان سی شارپ داره که بتونه بدون هنگ کردن اعداد اول بین 1 تا 1 میلیون رو پیدا کنه و در لیست باکس پاپ کنه ؟
من که هر روشی رو تست کردم کمتر ار 40 ثانیه جواب نمیده

با تشکر

Amir 2010a
دوشنبه 15 دی 1393, 17:17 عصر
لام
دوستان عزیز کسی برنامه ای به زبان سی شارپ داره که بتونه بدون هنگ کردن اعداد اول بین 1 تا 1 میلیون رو پیدا کنه و در لیست باکس پاپ کنه ؟
من که هر روشی رو تست کردم کمتر ار 40 ثانیه جواب نمیده


لطفا کمک حداقل روش و الگوریتم بهینه رو بگین

Share & Learn
دوشنبه 15 دی 1393, 17:57 عصر
یه برنامه دارم اعداد اول رو پیدا می کنه و سریعه اما اگه بخوای داخل تکست باکس نمایشش بدی زمان طولانی تر می شه
برنامه هایی که خودتون دارید و تست کردید هم احتمالا به این دلیل طولانی می شن که نمایششون می دید

ویرایش:

من فکر کردم 1000000امین عدد اول رو می خواین
برای اینی که شما می خواین اکثر برنامه ها سریع عمل می کنن، نمی دونم چه برنامه هایی رو تست کردید
برنامه ای که جناب Davidd (http://barnamenevis.org/member.php?313434-Davidd) دادند هم خیلی خوبه
تو برنامه ی ایشون اگر n رو برابر با 15485863 بذارید 1000000امین عدد اول رو هم به دست میاره!
موفق باشید

Davidd
دوشنبه 15 دی 1393, 19:43 عصر
با الگوریتم Sieve of Eratosthenes و نمایش اعداد در richTextBox (و البته استفاده از StringBuilder ) در کمتر از یک ثانیه اعدا اول پیدا میشه:

int n = 1000000;
bool[] A = new bool[n + 1];
for (int i = 2; i <= n; i++)
A[i] = true;
int sqrt = (int)Math.Sqrt(n) + 1;
for (int i = 1; i <= sqrt; i++)
{
if (A[i])
{
for (int j = i * i; j <= n; j += i)
A[j] = false;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++)
{
if (A[i])
sb.Append(i.ToString() + " , ");
}
richTextBox1.Text = sb.ToString();

Amir 2010a
سه شنبه 16 دی 1393, 07:39 صبح
به نظر من این روش ها برای محاسبه اعداد اول بزرگ ناکارآمد است
من این روش رو پیدا کردم اما زیاد نفهمیدم . دوستان عزیز کسی با این روش آشنایی داره وی یا برنامه نوشیه

Segmented sieve of Eratosthenes

Amir 2010a
سه شنبه 16 دی 1393, 17:11 عصر
Segmented sieve of Eratosthenes
کسی از دوستان با این روش آشنایی داره ؟ و یا حداقل الگوریتم و روش کارشو میدونه
با تشکر