PDA

View Full Version : مشکل در یافتن عدد اول



Amir 2010a
پنج شنبه 27 آذر 1393, 22:49 عصر
سلام
میدونیم یافتن اعداد اول سه یا چهر رقمی خیلی ساده استز (در حد کمتر از یک ثانیه )
اما اگر بخواییم 100 هزارمین عدد اول یا حتی 10 میلیونم امین عدد اول رو پیدا کینم چند دقیقه زمان میبره
آیا راهی برای یافتن آنی این عدد اول وجود داره ؟
از چه روشی باید استفاده کنم ؟
با تشکر

Share & Learn
پنج شنبه 27 آذر 1393, 23:24 عصر
سلام
تا جایی که من می دونم راه آنی که براش وجود نداره، با توجه به برنامه تون و سخت افزار و اینکه چندمین عدد رو می خواین یه زمانی می بره

Amir 2010a
جمعه 28 آذر 1393, 10:14 صبح
سلام
میدونیم یافتن اعداد اول سه یا چهر رقمی خیلی ساده استز (در حد کمتر از یک ثانیه )
اما اگر بخواییم 100 هزارمین عدد اول یا حتی 10 میلیونم امین عدد اول رو پیدا کینم چند دقیقه زمان میبره
آیا راهی برای یافتن آنی این عدد اول وجود داره ؟
از چه روشی باید استفاده کنم ؟
با تشکر
الگوریتم بهینه ای وجود نداره که در کمتر از ثانیه بتونه محاسبه کنه ؟

rahnema1
جمعه 28 آذر 1393, 20:09 عصر
سلام
توی یک تاپیک دیگه هم نوشته بودم البته از این بهینه تر هم میشه مثلا به صورت موازی در چند نخ اجرا بشه

int adadeaval(int TedadeAdadeAvval)
{
int[] aval = new int[TedadeAdadeAvval];
bool flag = true;
int number = 3;
aval[0] = 2;
int i = 1;
while(i < TedadeAdadeAvval)
{
int sagf = (int)Math.Sqrt(number);
for (int j = 0; aval[j] <= sagf; j++)
{
if (number % aval[j] == 0 )
{
flag = false;
break;
}
}
if (flag)
aval[i++] = number;
else
flag = true;
number += 2;
}
return aval[TedadeAdadeAvval-1];
}

Amir 2010a
جمعه 28 آذر 1393, 22:51 عصر
ممنون از لطف شما دوست عزیز
برای محاسبه 500 هزار امین عدد اول حدود 5 ثانیه زمان میبره که البته زمان زیاد بدی نیست

آیا روش بهینه تری با استفاده از روش غربالگری وجود نداره ؟

rahnema1
شنبه 29 آذر 1393, 20:32 عصر
بله روش بهتر هم هست
اینجا به زبان ++c
http://primesieve.org

Amir 2010a
یک شنبه 30 آذر 1393, 12:49 عصر
ممنون از لطف شما دوست عزیز
برای محاسبه 500 هزار امین عدد اول حدود 5 ثانیه زمان میبره که البته زمان زیاد بدی نیست

آیا روش بهینه تری با استفاده از روش غربالگری وجود نداره ؟


له روش بهتر هم هست
اینجا به زبان ++c
http://primesieve.org (http://primesieve.org/)
میتونید لطف کنید کد سی شارپ معادلشو بزارین لطفا
با تشکر

rahnema1
یک شنبه 30 آذر 1393, 23:38 عصر
به صورت dll کامپایل شده که می تونید تابعها را صدا بزنید.
فایل dll را در مسیر برنامه تون بذارید
http://www.sharefile.ir/uploads/1419285866.zip
اون که parallel هست باید سریعتر اجرا بشه. روی سیستم 32 بیتی تست کردم

using System;
using System.Runtime.InteropServices;

namespace prime
{
class Program
{
[DllImport("libprimesieve-5.4.1.dll")]
static extern UInt64 primesieve_nth_prime(UInt64 n, UInt64 start);
[DllImport("libprimesieve-5.4.1.dll")]
static extern UInt64 primesieve_parallel_nth_prime(UInt64 n, UInt64 start);
public static void Main(string[] args)
{
UInt64 res = primesieve_nth_prime(1000000,1);
Console.WriteLine("{0}",res);
res = primesieve_parallel_nth_prime(1000000,1);
Console.WriteLine("{0}",res);
Console.ReadKey(true);
}
}
}

rasol_afkham
دوشنبه 01 دی 1393, 11:07 صبح
میشه کمی درباره تابع های این Dll توضیح بدید ...؟ :متفکر:

Amir 2010a
دوشنبه 01 دی 1393, 14:27 عصر
ه صورت dll کامپایل شده که می تونید تابعها را صدا بزنید.
فایل dll را در مسیر برنامه تون بذارید
http://www.sharefile.ir/uploads/1419285866.zip

اون که parallel هست باید سریعتر اجرا بشه. روی سیستم 32 بیتی تست کردم

لطفا کد فایل dll رو بزارین

rahnema1
دوشنبه 01 دی 1393, 17:26 عصر
گفتم که سورس به زبان سی پلاس پلاس توی اون سایت که لینکش را گذاشتم موجوده
من فقط کامپایل کردم و dll را فرستادم خدمتتون

hamid_hr
دوشنبه 01 دی 1393, 19:58 عصر
من یه راه حل دارم
بیایم ایندکس گذاری کنیم
مثلا 100 تا عدد اول رو تو یه ارایه بزاریم
مثلا هزارمین عدد میشه x1
ده هزارمینش میشه x2
پنجاه هزارمینش میشه x3
,.......
همینطور تا 100 عدد
حالا طرف مثلا 20000 هزار رو بخواد میایم از x2 به بعد ده هزار تا میریم تا برسیم به عدد 20000
اینطوری سرعت خیلی خوب میشه فک کنم

FastCode
دوشنبه 01 دی 1393, 21:02 عصر
من یه راه حل دارم
بیایم ایندکس گذاری کنیم
مثلا 100 تا عدد اول رو تو یه ارایه بزاریم
مثلا هزارمین عدد میشه x1
ده هزارمینش میشه x2
پنجاه هزارمینش میشه x3
,.......
همینطور تا 100 عدد
حالا طرف مثلا 20000 هزار رو بخواد میایم از x2 به بعد ده هزار تا میریم تا برسیم به عدد 20000
اینطوری سرعت خیلی خوب میشه فک کنم

از این تکنیک ها زیاده.
من ۴ سال قبل ۵ ۶ تا روش محاسبه اعداد اول رو توی سایت گذاشتم که اگر پیدا کنید این هم توشن هست.
و روش ترکیب شدش با ایندکس دینامیک و استاتیک اولین اعداد اول.
بخوانید:
سورس کد libmath-prime-util-perl

Amir 2010a
سه شنبه 02 دی 1393, 19:32 عصر
یدونیم یافتن اعداد اول سه یا چهر رقمی خیلی ساده استز (در حد کمتر از یک ثانیه )
اما اگر بخواییم 100 هزارمین عدد اول یا حتی 10 میلیونم امین عدد اول رو پیدا کینم چند دقیقه زمان میبره
آیا راهی برای یافتن آنی این عدد اول وجود داره ؟
از چه روشی باید استفاده کنم ؟
با تشکر
دوستان عزیز برنامه نویس کسی از شما این مشکل رو نداره یا یک الگوریتم بهنه که بلافاصله بتونه بدون هنگ سسیتم یا صرف زمان زیاد بصورت آنی جواب بده لطفا

FastCode
سه شنبه 02 دی 1393, 21:54 عصر
دوستان عزیز برنامه نویس کسی از شما این مشکل رو نداره یا یک الگوریتم بهنه که بلافاصله بتونه بدون هنگ سسیتم یا صرف زمان زیاد بصورت آنی جواب بده لطفا

اونهایی که من گذاشتم برای بازه های اعداد تا int64 در نانو ثانیه جواب میدن.برای عدد n ام هم در مدت خیلی پایین جواب میدن.
اگر وقت و دست داشتم حتما یک نمونه با ایندکس براتون مینوشتم.

Amir 2010a
چهارشنبه 03 دی 1393, 10:38 صبح
اونهایی که من گذاشتم برای بازه های اعداد تا int64 در نانو ثانیه جواب میدن.برای عدد n ام هم در مدت خیلی پایین جواب میدن.
اگر وقت و دست داشتم حتما یک نمونه با ایندکس براتون مینوشتم.

ممنون ولی هیچ برنامه ای توی این سایت وجود نداره من همه شب کل سایت رو جستجو کردم
آیا میشه کد اونو یا لینکشو بزارین لطفا

Amir 2010a
چهارشنبه 03 دی 1393, 22:32 عصر
با چه الگوریتمی میشه تا چند میلیون امین عدد اول رو در خروجی چاپ کرد بدون اینکه سیستم هنگ کنه یا بیشتر از یک ثانیه زمان صرف بشه ؟
با تشکر

Amir 2010a
جمعه 05 دی 1393, 17:15 عصر
با چه الگوریتمی میشه تا چند میلیون امین عدد اول رو در خروجی چاپ کرد بدون اینکه سیستم هنگ کنه یا بیشتر از یک ثانیه زمان صرف بشه ؟
با تشکر
دوستان عزیز آیا الگوریتم بهینه ای برای این مسئله وجود داره یا نه
لطفا کمک کنید

FastCode
جمعه 05 دی 1393, 23:28 عصر
http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers
http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

nerset
جمعه 26 شهریور 1395, 21:40 عصر
بگذارید یک بار برای همیشه به بحث اعداد اول خاتمه بدهیم:
دوره های پدید آمدن اعداد اول در مجموعه اعداد درست مانند پدید آمدن خسوف یا کسوف می باشد و بزرگترین اشتباهی که تا کنون در ریاضیات اتفاق افتاده این بوده که خواستند به طور مستقیم بین دوره های پدید آمدن همه اعداد اول یک رابطه مستقیم پیدا کنند و به عبارتی به تمامی اعداد اول به یک چشم نگاه کرده و یک معادله واحد بین آنها پیدا کنند درست مثل اینکه بخواهیم برای پیش بینی دوره های پدید آمدن پدیده ای مانند کسوف یا خسوف یک رابطه زمانی مشخص پیدا کنیم و بدین ترتیب کسوف یا خسوف بعدی را پیش بینی کنیم در حالی که این کار یک اشتباه محض است و به راحتی می توان با داشتن معادلات حرکتی ماه و زمین و خورشید و پیدا کردن نقاط تلاقی این سه معادله ، این پدیده ها را پیش بینی کرد و درست به همین شکل هم می توان جایگاه بوجود آمدن اعداد اول را در بین مجموعه اعداد به طور صد در صد تعیین نمود به طوری که سه جزء ماه و زمین و خورشید در ابتدا به طور جداگانه وارد هر یک از مجموعه اعداد با یکان 1 و مجموعه اعداد با یکان 3 و مجموعه اعداد با یکان 7 و مجموعه اعداد با یکان 9 شده و نقش معادلات سازنده اعداد داخل آن مجموعه را خواهند داشت یعنی می توان گفت که ما در هر یک از این مجموعه اعداد ، دو و یا سه معادله سازنده تمامی اعداد موجود در آن مجموعه را داریم مثلا می توان گفت که تمامی اعداد داخل مجموعه اعداد غیر اول با یکان 9 فقط توسط سه تابع مولد با یکان 3*3 و 7*7 و 9*1 تولید می شوند که با پیدا کردن مکمل این سه تابع و اشتراک گیری بین آنها و یا حتی اشتراک گیری بین خروجی های آنها تمامی اعداد اول با یکان 9 را می توان به راحتی پیدا کرد که منظور از مکمل تابع یعنی تابعی است که می تواند اعدادی را که دارای یکان 9 بوده و توسط تابع مورد تولید نمی شود را تولید کند مثلا تابع مکمل برای تابع 2X همواره 2X+1 می باشد یعنی دقیقا اعدادی را که تابع اول پیدا نمی کند تابع دوم پیدا می کند .
در لینک مقاله زیر می توانید به طور کامل توابع ده گانه سازنده تمامی اعداد غیر اول موجود در چهار مجموعه ذکر شده را مشاهده کرده و نیز بدست آوردن توابع مکمل مربوط به مجموعه اعداد با یکان 9 را مشاهده نمایید که همان طور که گفته شد در مجموعه اعداد با یکان 9 ما سه تابع سازنده داریم که توابع مکمل مربوط به تابع 3*3 و نیز 7*7 و روش بدست آوردن آنها پیدا شده و فقط توابع مکمل 1*9 پیدا نشده است که با بدست آوردن آن می توان تمامی اعداد اول با یکان 9 را پیدا کرد.
از ویژگی های توابع مکمل 3*3 و 7*7 این است که خروجی های این توابع با وجود اینکه دارای یکان 9 هستند به هیچ وجه به اعدادی با یکان 3 و یا یکان 7 تجزیه نمی شوند و اعداد تولید شده توسط آنها یا فقط به اعدادی با یکان 1 و یا اعدادی با یکان 9 تجزیه شده و یا اینه اعدادی اول خواهند بود.
دلیل اینکه مکمل تابع 1*9 مهم است هم همین نکته می باشد که با پیدا کردن آن می توان پس از اشتراگ گیری با توابع مکمل دو تابع 3*3 و 7*7 همواره اعدادی را تولید کرد که دارای یکان 9 بوده و توسط هیچ یک از سه تابع سازنده اعداد غیر اول مجموعه اعداد با یکان 9 تولید نمی شود و در نتیجه به طور صد در صد عددی اول خواهد بود.

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

در ضمن برنامه کامپیوتری پیدا کردن این توابع مکمل را هم که به زبان ++C نوشته شده است را هم می توانید در انتهای این مقاله مشاهده کنید.
لازم به ذکر است که توسط این روش اعداد اولی با چندین هزار رقم به سرعت و به راحتی شناسایی شد و توسط روش های شناسایی اعداد اول صحت اول بودن آنها هم تایید شد.

http://screening-equations-numbers.blogsky.com

http://www.daneshju.ir/forum/f1315/t189150.html

http://www.daneshju.ir/forum/f1315/t189733.html#post877305

لازم به ذکر است که چون مکمل تابع 1*9 پیدا نشد بنابراین یک روش تصادفی برای این کار انتخاب شد که البته این روش به طور صد در صد جواب نمی داد و بنابراین از قاعده جبری خارج بود هر چند که امیدوارم در اینده یک روش منطقی برای پیدا کردن این تابع مکمل هم پیدا شده تا بتوان به طور صد در صد اعداد اولی با یکان 9 را تولید کرد به هر حال در شکل زیر روش تصادفی یاد شده را مشاهده می کنید که به از ورودی هایی به صورت 2 به توان x استفاده می کند تا شاید بتواند جای خالی مکمل تابع 1*9 را پر کند و همانطور که قبلا گفته شد این روش با وجود اینکه خروجی های اعداد اول زیادی تولید می کرد ولی نتوانست به طور صد در صدی اعداد اول تولید کند.
به هر حال همانطور که در مقالات مذکور هم مشاهده می کنید تابع 100X^2 + 160X + 59 یکی از توابع مکمل و در عین حال مشترک برای توابع 3*3 و 7*7 می باشد یعنی اینکه خروجی هایی که تولید می کند یا اعدادی اول بوده و یا اینکه فقط به اعدادی با یکان 1 و 9 قابل تجزیه می باشند.
همچنین همانطور که می بینید با قرار دادن عدد 2 به توان 2817 و یا امثال آن داخل این تابع مکمل می توان عددی اول با یکان 9 را تولید نمود.

سایت www.nerset.com در حال حاضر فعال نیست.

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

http://s2.picofile.com/file/7974178274/pishnama.png