سوال در مورد الگوریتم اعداد اول؟

**white fox** · یک شنبه 01 خرداد 1384, 13:41 عصر

استاد ما ازمون خواسته یه برنامه بنویسید که عددی از کاربر گرفته و مشخص کند این عدد اول هست یا خیر....
من به روش زیر برنامه رو نوشتم...البته در نظر داشته باشید که ما جلسه اولمون بود و چیز زیادی یادمون نداده ان...



Private Sub cmdTest_Click&#40;&#41;

Dim x As Integer

x = txtnum.Text



If &#40;x = 2&#41; Or &#40;x = 3&#41; Then

MsgBox "Yes...! this number is prime"

Exit Sub

End If



If &#40;x Mod 2&#41; = 0 Or &#40;x Mod 3&#41; = 0 Then

MsgBox "NO....! this number is not prime"

Else

MsgBox "Yes...! this number is prime"

End If

End Sub

مطمپنم الگوریتم بهتری هم هست...اگه میتونید کمک کنید..ممنون میشم

**3nitro** · یک شنبه 01 خرداد 1384, 14:29 عصر

این کدی که شما نوشتید فقط برای اعداد دو و سه و مضارب اونها چک میکنه . شما این رو باید درون یک حلقه قرار بدید که از 2 تا سر اون عدد ( نه خودش ) شروع کنه تقسیم کردن و باقیمونده صفر شد پس اول نیست در غیر این صورت اول است .

Private Sub cmdTest_Click&#40;&#41;

Dim x As Integer

Dim i As Integer

Dim R As Integer

x = txtnum.Text



If &#40;x = 2&#41; Or &#40;x = 3&#41; Then

MsgBox "Yes...! this number is prime"

Exit Sub

End If

For i=2 to x-1

R = x mod i

If R = 0 Then

MsgBox "NO....! this number is not prime"

Exit Sub

End If

Next i

MsgBox "Yes..!"

End Sub

**white fox** · یک شنبه 01 خرداد 1384, 16:11 عصر

درست میگید کد من برای اعدادی شبیه 77 ویا 55 درست کار نمیکنه...مممنونم

**hosseinzadeh** · یک شنبه 01 خرداد 1384, 19:28 عصر

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

#include&lt;stdio.h>

int n,k,i=2,flag=0;

int main&#40;&#41;

	&#123;

	printf&#40;"Enter the number"&#41;;

	scanf&#40;"%d",&amp;n&#41;;

	if &#40;n==2&#41;

		printf&#40;"Prime"&#41;;

	else

		&#123;

		do

			&#123;

			k=n%i;

			if &#40;k==0&#41;

				flag=1;

			i=i+1;

			&#125;

		while &#40;i&lt;n/2 &amp;&amp; flag==0&#41;;

		&#125;

	if &#40;flag==1&#41;

		printf&#40;"Not prime"&#41;;

	else

		printf&#40;"Prime"&#41;;

&#125;

**3nitro** · یک شنبه 01 خرداد 1384, 20:41 عصر

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

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

حتی میشه این رو به این صورت بیان کرد تا جذر اون عدد چک کنه ! :wink:

**رضا جاسبی** · شنبه 01 مرداد 1384, 15:35 عصر

من یک کم از تاریخ این تاپیک عقب هستم !
ولی برای اینکه تعیین کنیم که عددی اول هست یا نه راه درست این است که آن عدد را بر اعداد اول تا جذر آن عدد تقسیم کنیم. منظورم این است که i=i+1 در برنامه دوستمون hosseinzadeh می تواند تبدیل به NextPrime شود.
البته پیدا کردن عدد اول خودش یک مساله است. در واقع این روش برای یافتن تمام اعداد اول مثلا کوچکتر از 1000 خوب است.

**seyedof** · شنبه 01 مرداد 1384, 20:22 عصر

سلام
همیشه لیست اعداد اولی که پیدا شده رو نگه دارید تا تقسیم پذیری اعداد جدید فقط بر اوونها آزمایش بشه.
ضمنا لازم نیست همه اعداد رو تست کنید. طبق یک قضیه ریاضی کلیه اعداد اول به صورت 6k+-1 هستند. یعنی در بهترین حالت فقط یک سوم اعداد طبیعی میتونن اول باشند (البته در عمل خیلی کمتر از اینه)
ممنون علی

**Sepidar** · شنبه 01 مرداد 1384, 20:54 عصر

طبق یک قضیه ریاضی کلیه اعداد اول به صورت 6k+-1 هستند.

خسته نباشید! شما فقط مضارب 2 و 3 رو حذف کردید

**3nitro** · یک شنبه 02 مرداد 1384, 14:50 عصر

پیدا کردن عدد اول خودش یک مساله است

کد کاملی در این زمینه در بخش ASP هست که آقای غیبی نوشتند . خیلی کامل هست و در بازه ای که مشخص می کنید بهتون اعداد اول رو نشون میده . میتونید اون رو هم نگاهی بندازید .

**seyedof** · دوشنبه 03 مرداد 1384, 19:39 عصر

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

خسته نباشید! شما فقط مضارب 2 و 3 رو حذف کردید

سلامت باشید :)

بله ولی وقتی میگویند اعداد اول از یک تا فلان رو پیدا کنید معمولا خیلی ها اعداد فرد رو چک میکنند یعنی فقط یک دوم اعداد چک میشوند اما در صورتی که فقط اعداد بصورت 6k+-1 رو چک کنید یک سوم اعداد چک میشوند یعنی اگر مثلا تا ده میلیون جلو برید فرق این دو تا میشه ۶/۱ میلیون عدد یا افزایش ۱۶ درصدی در سرعت که اصلا چیز کمی نیست.
تا جایی که بنده اطلاع دارم بیش از نمیشه اعداد رو فیلتر اولیه کرد چون فرمولی کلی تر از این برای اعداد اول وجود ندارد.
پس چندان هم پیش پا افتاده نبود :)
ممنون علی

**3nitro** · دوشنبه 03 مرداد 1384, 21:53 عصر

کلیه اعداد اول به صورت 6k+-1 هستند.

ببخشید k چه مجموعه ای هست ؟ تازه اینجوری حرف Sepidar درست تر هست .

**seyedof** · چهارشنبه 05 مرداد 1384, 11:30 صبح

نوشته شده توسط 3nitro

ببخشید k چه مجموعه ای هست ؟ تازه اینجوری حرف Sepidar درست تر هست .

سلام
اینکه جزو بدیهیات است. کلیه اعداد اول به صورت 6k+-1 هستند. k که خب معلومه عدد طبیعیه دلخواه است. ضمنا اینجا بحث درستی و غلطی نیست. من روشی گفتم که در ادامه روشهای دوستان بود و سرعت برنامه رو افزایش میداد Optimization. این امر به صورت علمی تئوری و عملی قابل آزمایش است.
ممنون علی

**mnajafi** · شنبه 08 مرداد 1384, 19:21 عصر

دوستان تا اونجایی که من شنیدم هیچ فرمول خاصی برای اعداد اول پیدا نشده .یعنی با قطعیت نمی شه گفت که اعداد اول از قانون خاصی تبعیت می کنند.رجوع شود به مجلات ریاضی از دو سه ماه پیش به این ور که بزرگترین عدد اول با چند میلینو رقم رو پیدا کرده بودند.در هر حال برای اینکه سرعت محاسبه برنامه بالا بره اگر یک عدد رو از 2 تا جذر خودش تقسیم کنیم باقیمانده صفر بشه عدد اول نیست در غیر این صورت هست.

**someCoder** · یک شنبه 09 مرداد 1384, 00:00 صبح

بازم رسیدیم به همین بحث بزرگترین عدد اول! تورو خدا یکی لینک این مطلب رو به من بده!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!
هر چی گشتم پیدا نکردم

**seyedof** · یک شنبه 09 مرداد 1384, 14:23 عصر

سلام
در ریاضیات کلمه به کلمه تعاریف مهم هستند. من هم گفتم هر عدد اول به صورت 6k+-۱ است نه اینکه هر ۶k+-1 ای عدد اول است. اثباتش در تئوری اعداد خیلی هم ساده است.
برای بالا بردن سرعت پیدا کردن اعداد اول روشهایی هست که در این تاپیک بعضی هاشون توضیح داده شد.
ممنون علی

**someCoder** · پنج شنبه 20 مرداد 1384, 00:11 صبح

آآآآآآآآآآآآِی! کمکککککککککککککک!
بابا یکی لینک این قضیه آخرین عدد اول رو بگه! نگین هم بگرد که گشتم و نیافتم

**mnajafi** · پنج شنبه 20 مرداد 1384, 12:23 عصر

http://www.irna.ir/index.php?lang=fa..._texts=checked

این هم لینک

**samy_th_1363** · یک شنبه 23 مرداد 1384, 18:35 عصر

Private sub command1_click()
Dim x As Long
x = Text1
Dim i As Long
For i = 2 To x \ 2
If x Mod i = 0 Then
Print "not prime"
Exit Sub
End If
Next i
Print "prime"
End Sub
اینم یه نوع جواب هست

**mnajafi** · دوشنبه 24 مرداد 1384, 09:26 صبح

شما در این مسئله تا n/2 رو چک می کنید .اگه یه عدد خیلی بزرگ باشه اونوقت کل زمان برنامه برای این کار تلف می شه.اگه شما یه عدد غیر از خودش ویک رو پیدا کنید که n بر اون بخش پذیر باشه شرط نقض می شه. برای این کار بهتره از 2 تا جذر عدد n رو چک کنیم.هم دامنه اعداد کوچکتره وهم جواب سریعتر پیدا میشه.

if n=2 or 3 is prime
for i=2 to sqr n
if n mod i =0 is not prime
else is prime

**TAHEREH** · چهارشنبه 27 مهر 1384, 08:15 صبح

1 - شروع
2- a راازورودی بگیر
3 - 1=i و k=0
4 - a mod i=0 آنگاه k=k+1
5 - i=i+1
6 = اگرi<=a آنگاه چاپ کن عدد اول است درغیراینصورت چاپ کن اول نیست
7 - پایان

**mzjahromi** · چهارشنبه 27 مهر 1384, 08:44 صبح

این روش هم بد نیست



int isprime(int x)

{

    int i;

    for(i=2;i<x/2;i++)

       if ((x%i)==0)

         return 0;

    return 1;

}

**Jason.Bourne** · شنبه 09 آذر 1387, 12:59 عصر

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

برای این کار بهتره از 2 تا جذر عدد n رو چک کنیم.

لطف میکنید در این مورد توضیح بدید؟
متوجه منظور شما نشدم.

**gelayor14** · یک شنبه 16 آبان 1389, 10:51 صبح

با سلام
به نظر شما این الگوریتم چی می شود؟
الگوریتمی که عدد n را از ورودی دریافت کرده و و n امین عدد اول را شناسایی و چاپ کند

**returnx** · یک شنبه 16 آبان 1389, 18:51 عصر

الگوریتمی که عدد n را از ورودی دریافت کرده و و n امین عدد اول را شناسایی و چاپ کند

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

**silverfox** · یک شنبه 16 آبان 1389, 22:10 عصر

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

**gelayor14** · دوشنبه 17 آبان 1389, 20:32 عصر

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

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

فرض کنید عدد 10 از ورودی خوانده شده-10 امین عدد اول یعنی 29 را چاپ کند

**silverfox** · سه شنبه 18 آبان 1389, 13:54 عصر

با یه while تا موقعی که به مثلا 10مین عدد اول نرسیده عدد ها رو به ترتیب(یا مضارب قبلی ها رو کنار می ذارین)چک می کنین که اول هست یا نه تا به جواب برسین

نام تاپیک: سوال در مورد الگوریتم اعداد اول؟

ابزار های تاپیک

نمایش

سوال در مورد الگوریتم اعداد اول؟

الگوریتم

نقل قول: سوال در مورد الگوریتم اعداد اول؟

نقل قول: سوال در مورد الگوریتم اعداد اول؟

نقل قول: سوال در مورد الگوریتم اعداد اول؟

نقل قول: سوال در مورد الگوریتم اعداد اول؟

نقل قول: سوال در مورد الگوریتم اعداد اول؟

نقل قول: سوال در مورد الگوریتم اعداد اول؟

قوانین ایجاد تاپیک در تالار