PDA

View Full Version : سوال در مورد الگوریتم اعداد اول؟



white fox
یک شنبه 01 خرداد 1384, 13:41 عصر
استاد ما ازمون خواسته یه برنامه بنویسید که عددی از کاربر گرفته و مشخص کند این عدد اول هست یا خیر....
من به روش زیر برنامه رو نوشتم...البته در نظر داشته باشید که ما جلسه اولمون بود و چیز زیادی یادمون نداده ان...



Private Sub cmdTest_Click()
Dim x As Integer
x = txtnum.Text

If (x = 2) Or (x = 3) Then
MsgBox "Yes...! this number is prime"
Exit Sub
End If

If (x Mod 2) = 0 Or (x Mod 3) = 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()
Dim x As Integer
Dim i As Integer
Dim R As Integer
x = txtnum.Text

If (x = 2) Or (x = 3) 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<stdio.h>
int n,k,i=2,flag=0;
int main()
{
printf("Enter the number");
scanf("%d",&n);
if (n==2)
printf("Prime");
else
{
do
{
k=n%i;
if (k==0)
flag=1;
i=i+1;
}
while (i<n/2 && flag==0);
}
if (flag==1)
printf("Not prime");
else
printf("Prime");
}

3nitro
یک شنبه 01 خرداد 1384, 20:41 عصر
می تونی اول برای 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 عصر
خسته نباشید! شما فقط مضارب 2 و 3 رو حذف کردید

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

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

3nitro
دوشنبه 03 مرداد 1384, 21:53 عصر
کلیه اعداد اول به صورت 6k+-1 هستند.ببخشید k چه مجموعه ای هست ؟ تازه اینجوری حرف Sepidar درست تر هست .

seyedof
چهارشنبه 05 مرداد 1384, 11:30 صبح
ببخشید 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&option=com_newssearch&task=search&searchtext=%D8%B9%D8%AF%D8%AF+%D8%A7%D9%88%D9%84&sLines=0&x=0&y=0&i_titles=checked&i_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 عصر
برای این کار بهتره از 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 عصر
سوال نا مفهوم !!!
لطفا یکم بیشتر توضیح بدید...

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

silverfox
سه شنبه 18 آبان 1389, 13:54 عصر
با یه while تا موقعی که به مثلا 10مین عدد اول نرسیده عدد ها رو به ترتیب(یا مضارب قبلی ها رو کنار می ذارین)چک می کنین که اول هست یا نه تا به جواب برسین