PDA

View Full Version : محاسبه 1000 امین عدد اول



Amir 2010a
جمعه 02 آبان 1393, 21:44 عصر
سلام
من میخوام یک برنامه با سی شارپ بنویسم که اعداد اول رو محاسبه کنه و بریزه تو یک کمبوباکس تا برسه به هزارمین عدد اول و محاسبه متوقف بشه اما برنامه ای که نوشتم خیلی سریع سرعت اجراش کم میشه و زیاد روی پردازنده و رم تاثیر میزاه
لطفا اگه میشه در مورد روش کار و الگوریتم بهینه این مسئله توضیح بدین
با تشکر

Share & Learn
جمعه 02 آبان 1393, 22:25 عصر
سلام
این الگوریتم رو ببینید





ویرایش:

این روش ها بهینه نیست و زمان زیادی رو برای اجرا میگیره
حالا اکر به جای n عدد 2000 بزاریم یعنی قرار باشه برنامه دو هزارمین عدد اول رو چاپ کنه یک ساعت یا بیشتر زمان میگیره !!!
روش بهتری وجود نداره ؟

دوست عزیز شما اصلا برنامه ای من دادم رو دیدی؟
برنامه ای که فرستادم 3000 امین عدد اول رو کمتر از 30 ثانیه می ده...

khokhan
جمعه 02 آبان 1393, 22:38 عصر
سلام

لطفا اگه میشه در مورد روش کار و الگوریتم بهینه این مسئله توضیح بدین
با تشکر
....................................

public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void FindPrimeNumber()
{
int topNumber = 1000;
var numbers = new BitArray(topNumber, true);

for (int i = 2; i < topNumber; i++)
if (numbers[i])
{
for (int j = i * 2; j < topNumber; j += i)
numbers[j] = false;
}

int primes = 0;

for (int i = 1; i < topNumber; i++)
if (numbers[i])
{
primes++;
comboBox1.Items.Add(i);
}


}
private void Form1_Load(object sender, EventArgs e)
{
FindPrimeNumber();
}
}

Amir 2010a
پنج شنبه 22 آبان 1393, 06:54 صبح
این روش ها بهینه نیست و زمان زیادی رو برای اجرا میگیره
حالا اکر به جای n عدد 2000 بزاریم یعنی قرار باشه برنامه دو هزارمین عدد اول رو چاپ کنه یک ساعت یا بیشتر زمان میگیره !!!

روش بهتری وجود نداره ؟

rahnema1
پنج شنبه 22 آبان 1393, 10:41 صبح
این روش را امتحان کنید

int TedadeAdadeAvval = 2000;
List<int> aval = new List<int>();
bool flag = true;
int i = 3;
aval.Add(2);
while(aval.Count < TedadeAdadeAvval)
{
foreach (var element in aval)
{
if (element > i / element )
break;
if (i % element == 0 )
{
flag = false;
break;
}
}
if (flag)
aval.Add(i);
else
flag = true;
i++;
}
comboBox1.DataSource = aval;