الگوریتم سریع یافتن اعداد اول بدون تقسیم

[tooraj_azizi_1035]

با سلام،
روش فرار از تقسیم و استفاده از درخت حالت (State Tree)
یک روش برای تشخیص اعداد اول هست که می خوام نظراتتون رو بدید. x عدد مورد نظر هست.

بعد از اینکه مطمئن شدیم رقم یکان عدد 1،3،7 یا 9 هست سعی می کنیم دو عدد رو که ضرب اونها برابر x میشه رو پیدا کنیم. اگه این دو عدد پیدا شد عدد اول نیست در غیر این صورت اوله.

x=4654123

یک جدول داریم که حالت هایی که حاصل ضرب دو عدد تک رقمی که یکانش 3 (هر 4 حالت را داریم) می شود را از آن می خوانیم. a,b دو عدد فرضی هستند.
حالت اول:
6 (رقم نقلی)
9?????
x
?????7
------------
3?????

حالت بعدی 3 و 1 است و ...
می توان این هر حالت را به 1 نخ اجرایی داد. نخ های اجرایی شاخه های یک درخت و گره هایشان را ایجاد می کنند. یک شاخه از این درخت یک حالت مانند حالت بالا را بررسی می کند. هر کدام از نخ های اجرایی که به صورت موازی اجرا می شوند بتوانند به دو عدد برسند تمام نخ ها متوقف و نتیجه این است که عدد اول نیست.
توضیحات بالا به شکل گذرا گفته شده و با پیاده سازی الگوریتم در یک زبان برنامه نویسی تمام جزئیات معلوم می شود.
این الگوریتم در حد تئوری باقی مونده و هنوز پیاده سازیش نکردم.
توضیحات بیشتر را در گفتگو برای دوستان علاقه مند خواهم داد.

[mehmir]

من فکر کنم خیلی زمان بر باشه
مثلا واسه مثال خودتون که یه عدد 7 رقمیه تعداد حالتایی که میشه در نظر گرفت برابر با تعداد جوابهای m+n=7 که هر کدوم از اونا باز حالتای خودشو داره
اما نظرم اینکه ادامش بدین شاید بشه باش یه مقاله داد

[xxxxx_xxxxx]

سلام،
من اصلاً متوجه نشدم! اگر ممکنه بیشتر توضیح بدید.

بعد از اینکه مطمئن شدیم رقم یکان عدد 1،3،7 یا 9 هست سعی می کنیم دو عدد رو که ضرب اونها برابر x میشه رو پیدا کنیم. اگه این دو عدد پیدا شد عدد اول نیست در غیر این صورت اوله.

چرا 1 و 3 و 7 و 9 ؟

این قسمت رو هم اصلاً متوجه نشدم!

یک جدول داریم که حالت هایی که حاصل ضرب دو عدد تک رقمی که یکانش 3 (هر 4 حالت را داریم) می شود را از آن می خوانیم. a,b دو عدد فرضی هستند.
حالت اول:
6 (رقم نقلی)
9?????
x
?????7
------------
3?????

حالت بعدی 3 و 1 است و ...

[مسعود اقدسی فام]

سلام،
من اصلاً متوجه نشدم! اگر ممکنه بیشتر توضیح بدید.


چرا 1 و 3 و 7 و 9 ؟

هر عدد زوجی حداقل بر عدد 2 بخشپذیره. پس اگر عددی زوج بود، حتما اول نیست (غیر از خود 2 البته). عدد زوج هم رقم یکانش زوج می‌شه. یعنی صفر و 2 و 4 و 8.

[tooraj_azizi_1035]

سلام،
ببخشید،
راستش این الگوریتم فعلاً در حد ایده هست و هنوز کامل پیاده سازیش نکردم و روش کار هم به این صورت هست که ما سعی می کنیم دو عدد رو پیدا کنیم که ضرب اونها برابر با عدد مورد نظر (x) باشه. اگه این دو عدد پیدا بشه اون عدد (x) اول نیست در غیر این صورت اوله.
در مورد اون قسمتی که شما گفتید متوجه نشدم، ما می خواهیم عدد فرضی اول یعنی 9?????? را در عدد فرضی دوم 7????? ضرب کنیم. اینکه می گوئیم حالت اول 7 و 9 به این دلیل است که ضرب آنها 63 می شود و از این طریق مطمئن می شویم که دو عدد فرضی که رقم یکان آنها فرد است رقم یکان حاصلضرب آنها حتما 3 می شود. علامت سوال جای خالی ارقام دو عدد فرضی است. این تلاش برای یافتن دو عدد ادامه پیدا می کند. یعنی بدست آوردن علامت سوال های بعدی برای یافتن دو عدد فرضی.
حالت بعدی ما 9 و 7 است. و حالت های بعدی ضرب هر دو عدد تک رقمی است که رقم یکان حاصلضرب آنها برابر 3 است.
امیدوارم متوجه شده باشید.

[مسعود اقدسی فام]

سلام،
ببخشید،
راستش این الگوریتم فعلاً در حد ایده هست و هنوز کامل پیاده سازیش نکردم و روش کار هم به این صورت هست که ما سعی می کنیم دو عدد رو پیدا کنیم که ضرب اونها برابر با عدد مورد نظر (x) باشه. اگه این دو عدد پیدا بشه اون عدد (x) اول نیست در غیر این صورت اوله.
در مورد اون قسمتی که شما گفتید متوجه نشدم، ما می خواهیم عدد فرضی اول یعنی 9?????? را در عدد فرضی دوم 7????? ضرب کنیم. اینکه می گوئیم حالت اول 7 و 9 به این دلیل است که ضرب آنها 63 می شود و از این طریق مطمئن می شویم که دو عدد فرضی که رقم یکان آنها فرد است رقم یکان حاصلضرب آنها حتما 3 می شود. علامت سوال جای خالی ارقام دو عدد فرضی است. این تلاش برای یافتن دو عدد ادامه پیدا می کند. یعنی بدست آوردن علامت سوال های بعدی برای یافتن دو عدد فرضی.
حالت بعدی ما 9 و 7 است. و حالت های بعدی ضرب هر دو عدد تک رقمی است که رقم یکان حاصلضرب آنها برابر 3 است.
امیدوارم متوجه شده باشید.

الگوریتم رایج چک کردن اول بودن یک عدد از مرتبه‌ی رادیکال عدده. کافیه عدد مورد نظر به اعداد دو تا کف رادیکالش بخشپذیر نباشه. مرتبه‌ی اجرایی الگوریتم مورد نظر شما کمتر از اینه؟

[Salar Ashgi]

البته روشهایی هست که میشه مرتبه زمانی الگوریتم رو کاهش داد و الگوریتم رو بهینه تر کرد :

• هر عدد اول به جز 2 و 3 بصورت 6k+1 و 6k-1 میباشد که k عددی صحیح است .
• مربع هر عدد اول بشکل 24k+1 میباشد .
• شرط رقم یکان
• بهینه سازی حلقه ای که قراره تا رادیکال عدد مورد نظر برود .
• و ...

ادغام متودهای بالا ، میتواند الگوریتمی بهینه ایجاد کند .

در ضمن مطالعه مطلب زیر نیز خالی از لطف نخواهد بود :
http://en.wikipedia.org/wiki/Prime_testing