هل هناك طريقة للعثور على القيمة التقريبية للعدد الأولي n؟

Question

هل هناك دالة تقوم بإرجاع القيمة التقريبية لـ ن رئيس الوزراء؟أعتقد أن هذا سيكون بمثابة دالة تقريبية للعد الأولي العكسي.على سبيل المثال، إذا أعطيت هذه الدالة 25 فسوف تُرجع رقمًا حوالي 100، أو إذا أعطيت هذه الدالة 1000 فسوف تُرجع رقمًا حوالي 8000.لا يهمني إذا كان الرقم الذي تم إرجاعه أوليًا أم لا، لكنني أريده أن يكون سريعًا (لذلك لا يتم إنشاء الرقم الأول ن الأعداد الأولية لإرجاع ن ذ.)

أود هذا حتى أتمكن من إنشاء الأول ن الأعداد الأولية باستخدام المنخل (إراتوستينس أو أتكين).ولذلك فإن التقريب ل ن من الأفضل ألا نقلل أبدًا من قيمة الشيء الفعلي ن رئيس الوزراء.

(تحديث:يرى إجابتي للحصول على طريقة جيدة للعثور على الحد الأعلى لل ن العدد الأولي.)

Answer 1

حدود أكثر صرامة:

static const unsigned short primes_small[] = {0,2,3,5,7,11};

static unsigned long nth_prime_upper(unsigned long n) {
  double fn = (double) n;
  double flogn, flog2n, upper;
  if (n < 6)  return primes_small[n];
  flogn  = log(n);
  flog2n = log(flogn);

  if      (n >= 688383)    /* Dusart 2010 page 2 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
  else if (n >= 178974)    /* Dusart 2010 page 7 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
  else if (n >=  39017)    /* Dusart 1999 page 14 */
    upper = fn * (flogn + flog2n - 0.9484);
  else                    /* Modified from Robin 1983 for 6-39016 _only_ */
    upper = fn * ( flogn  +  0.6000 * flog2n );

  if (upper >= (double) ULONG_MAX) {
     /* Adjust this as needed for your type and exception method */
    if (n <= 425656284035217743UL) return 18446744073709551557UL;
    fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
  }

  return (unsigned long) ceil(upper);
}

يجب ألا تكون هذه أقل من nth_prime الفعلي، ويجب أن تعمل مع أي إدخال 64 بت، وأن تكون ذات حجم أو أقرب من الصيغة الواردة من Robin مسبقًا (أو صيغة Wimblik المعقدة ذات النطاق المحدود).لاستخدامي، لدي جدول أعداد أولية صغيرة أكبر قليلاً حتى أتمكن من تشديد التقدير الأخير أكثر قليلاً.من الناحية الفنية، من الصيغ يمكننا استخدام Floor() بدلاً من ceil() ولكني قلق بشأن الدقة.

يحرر:هناك خيار آخر لتحسين هذا قليلاً وهو تنفيذ حدود عدد أولية جيدة (على سبيل المثال.Axler 2014) وإجراء بحث ثنائي عليها.يستغرق الكود الخاص بهذه الطريقة حوالي 10x أطول من ما سبق (لا يزال يعمل في أقل من مللي ثانية)، ولكن يمكن أن يقلل نسبة الخطأ بترتيب من حيث الحجم.

إذا كنت تريد تقديرًا للعدد الأولي، فيمكنك القيام بما يلي:

• سيبولا 1902 (انظر دوسارت 1999 الصفحة 12 أو هذه الورقة.أجد أن ثلاثة حدود (م = 2) بالإضافة إلى عامل تصحيح من الدرجة الثالثة مفيدة، ولكن مع وجود عدد أكبر من الحدود، فإنها تتأرجح كثيرًا.الصيغة الموضحة في رابط ويكيبيديا هي هذه الصيغة (مع م = 2).إن استخدام معكوس li ذو الحدين أو معكوس Riemann R أدناه سيعطي نتائج أفضل.
• قم بحساب الحدود العليا والدنيا لـ Dusart 2010 ومتوسط ​​النتائج.ليس سيئًا للغاية، على الرغم من أنني أظن أن استخدام المتوسط ​​المرجح سيعمل بشكل أفضل لأن الحدود ليست ضيقة بنفس القدر.
• li^{-1}(n) نظرًا لأن li(n) هو تقريب مناسب للعدد الأولي، فإن المعكوس هو تقريب جيد nth_prime.يمكن إجراء هذا وكل ما تبقى بسرعة إلى حد ما كبحث ثنائي عن الوظيفة.
• li^{-1}(n) + li^{-1}(sqrt(n))/4 أقرب، لأن هذا يقترب من R(n)
• R^{-1} دالة Riemann R العكسية هي أقرب متوسط ​​تقريبي أعرف أنه معقول.

أخيرًا، إذا كانت لديك طريقة سريعة جدًا للعد الأولي، مثل أحد تطبيقات LMO (توجد الآن ثلاثة تطبيقات مفتوحة المصدر)، فيمكنك كتابة طريقة nth_prime سريعة ودقيقة.يمكن إجراء حساب العدد 10^10 في بضعة أجزاء من الثانية، وحساب العدد 10^13 في بضع ثوانٍ (على جهاز سريع حديث).تكون التقريبات سريعة للغاية في جميع الأحجام وتصلح لأعداد أكبر بكثير، ولكن كل شخص لديه فكرة مختلفة عما تعنيه كلمة "كبير".

Answer 2

وشكرا لجميع من تلك الإجابات. كنت أظن أن هناك شيئا بسيطا نوعا ما من هذا القبيل، ولكن أنا لا يمكن العثور عليه في ذلك الوقت. لقد فعلت المزيد من الأبحاث قليلا جدا.

وكما أريد ل غربال لتوليد أول <م > ن الأعداد الأولية، أريد التقريب لتكون أكبر من أو يساوي <م> ن مقتبل العشرين. (لذلك، أريد الحد العلوي من ن عدد الوزراء ال.)

ويكيبيديا يعطي الحد الأعلى التالية لn >= 6

p_n <= n log n + n log log n   (1)

وحيث p_n هو ن مقتبل العشرين، وlog هو اللوغاريتم الطبيعي. وهذا هو بداية جيدة، ولكنها يمكن أن نبالغ بمقدار لا يستهان به. هذه المقالة في <لأ href = "HTTP: // شبكة الاتصالات العالمية. maa.org/pubs/cmj.html "يختلط =" نوفولو noreferrer "> وكلية الرياضيات مجلة يعطي تشديد الحد الأعلى لn >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

وهذا هو أكثر تشددا بكثير ملزمة كما يظهر في الجدول التالي

n         p_n         approx 1    error%  approx 2    error%
1         2                            
10        29          31          6.90 
100       541         613         13.31
1000      7919        8840        11.63
10000     104729      114306      9.14    104921      0.18
100000    1299709     1395639     7.38    1301789     0.16
1000000   15485863    16441302    6.17    15502802    0.11
10000000  179424673   188980382   5.33    179595382   0.10

وأنا نفذت بلدي <م> ن وظيفة تقريب الرئيسية لاستخدام التقريب الثاني لn >= 7022، أول تقدير تقريبي ل6 <= n < 7022، وبحث مجموعة ل5 الأعداد الأولية الأولى عشر.

و(على الرغم من أن الأسلوب الأول هو ليس ملزما ضيق جدا، خاصة بالنسبة للمجموعة حيث يمكنني استخدام ذلك، وأنا لست قلقا كما أريد هذا لغربال، ومنخل من أعداد أصغر رخيص حسابيا.)

Answer 3

برايم نظرية عدد يعطي عددا من الأعداد الأولية أقل من قيمة العتبة، لذلك يمكن أن يكون تستخدم لإعطاء قيمة تقريبية لرئيس الوزراء الألف.

Answer 4

كتقدير تقريبي، يمكنك استخدام n*ln(n) كتقدير تقريبي للعدد الأولي n.هناك طريقة أكثر تعقيدًا ولكنها أكثر دقة، ويمكنك العثور على تفاصيلها على ويكيبيديا هنا.

Answer 5

وبلدي أفضل رئيس (ن) تقدير

1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))

إليك بلدي أحدث صيغة أكثر التجريبية. بالمناسبة. هو رئيس الوزراء 10000000000000 323,780,508,946,331 تعمل هذه الصيغة بشكل جيد جدا في هذا النطاق غير متأكد إذا ما استمر في الاقتراب من n*ln(n)+n*(ln(ln(n))-0.9385).

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))

Answer 6

وتطبيق فعال وربما غير ممكن مع غربال. أعتقد أن ما يمكن أن يحدث إذا كنت تريد أن يكون أول 10.000 الأعداد الأولية. وربما كنت قد لجعل غربال على كمية أكبر الضخم من الأرقام.

وimplentation الخاصة بك في هذا السؤال و <لأ href = "https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043007#1043007">my الإجابة طرق جيدة لتنفيذ هذا دون معرفة حوالي. قيمة مقتبل

Answer 7

لتكمل ملزمة العليا دانا J في هذه الصيغة يجب أن تعطيك جيدة الأدنى.

P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;