الأكثر كفاءة رمز لأول 10000 رئيس الوزراء الأرقام ؟
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أريد أن طباعة أول 10000 الأعداد الأولية.يمكن لأي شخص أن تعطيني أكثر كفاءة رمز هذا ؟ التوضيحات:
- لا يهم إذا كان الكود غير فعال ل ن >10000.
- حجم رمز لا يهم.
- لا يمكنك مجرد رمز القرص الثابت القيم في أي شكل من الأشكال.
المحلول
غربال من آتكن ربما هو ما تبحث عنه ، الحد الأعلى تشغيل الوقت O(N/log log N).
إذا كنت تعمل فقط الأرقام من 1 أكثر من 1 أقل من مضاعفات الرقم 6, يمكن أن يكون حتى أسرع ، حيث أن جميع الأعداد أعلاه 3 1 بعيدا عن بعض متعددة من ستة.مورد بياني
نصائح أخرى
أوصي غربال ، إما غربال إراتوستينس أو غربال آتكن.
غربال أو إراتوستينس هو على الأرجح الأكثر بديهية طريقة العثور على قائمة من الأعداد الأولية.أساسا كنت:
- كتابة قائمة من الأرقام من 2 إلى أي حد تريد ، دعونا نقول 1000.
- أخذ الرقم الأول ليس عبرت قبالة (لأول التكرار هذا هو 2) و شطب جميع مضاعفات هذا العدد من القائمة.
- كرر الخطوة 2 حتى تصل إلى نهاية القائمة.جميع الأرقام التي لا تكف رئيس الوزراء.
من الواضح أن هناك عدد غير قليل من التحسينات التي يمكن القيام به لجعل هذه الخوارزمية تعمل بشكل أسرع, ولكن هذه هي الفكرة الأساسية.
غربال من آتكن يستخدم نهجا مماثلا ، ولكن للأسف أنا لا أعرف ما يكفي عن ذلك أن أشرح لك.ولكن أنا أعرف أن الخوارزمية أنا مرتبط يأخذ 8 ثوان لمعرفة كل يعبي تصل إلى 1000000000 على قديم بنتيوم II-350
غربال إراتوستينس البرمجية المصدر: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
غربال آتكن البرمجية المصدر: http://cr.yp.to/primegen.html
هذا ليس صارما ضد hardcoding قيود ، ولكن يأتي بشكل رهيب قريب.لماذا لا برمجيا تحميل هذه القائمة وطباعته ، بدلا من ذلك ؟
GateKiller, كيف حول إضافة break إلى أن if في foreach الحلقة ؟ التي من شأنها تسريع الأمور الكثير لأنه إذا كان مثل 6 يقبل القسمة على 2 لا تحتاج إلى تحقق مع 3 و 5.(أنا أصوت الحل الخاص بك على أي حال إذا كان لدي ما يكفي من سمعة :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
في هاسكل, يمكننا كتابة كلمة كلمة تقريبا الرياضية تعريف غربال إراتوستينس،"الأعداد الأولية هي الأعداد الطبيعية 1 أعلاه دون أي أرقام المركبة ، حيث المركبة تم العثور عليها عن طريق تعداد كل رئيس مضاعفات":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 هو شبه لحظية.
المراجع:
رمز أعلاه بسهولة أنب إلى العمل على الاحتمالات فقط ، primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).تعقيد الوقت تحسنت كثيرا (فقط حوالي سجل العامل الأمثل أعلاه) قبل للطي في هيكل شجرة تشبه والفضاء التعقيد تحسين جذري قبل متعدد المراحل يعبي الإنتاج, في
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(في هاسكل الأقواس تستخدم في تجميع استدعاء دالة تدل فقط عن طريق التجاور ، (:) هو سلبيات مشغل القوائم ، (.) هو التركيب الوظيفي المشغل: (f . g) x = (\y -> f (g y)) x = f (g x)).
@مات:سجل(سجل(10000)) هو ~2
من ويكيبيديا المادة (الذي استشهد) غربال آتكن:
هذا غربال يحسب يعبي حتى ن باستخدام
O(N/log log N)العمليات مع فقط N1/2+o(1) بت من الذاكرة.هذا هو أفضل قليلا من غربال إراتوستينس الذي يستخدمO(N)عمليات O(N1/2(log log N)/log ن) بت من الذاكرة (A. O. L.لآتكن دي جيبيرنشتاين ، 2004).هذه مقارب الحسابية تشمل التعقيدات بسيطة التحسينات مثل عجلة القيادة التعميل و تقسيم حساب إلى كتل أصغر.
نظرا مقارب الحسابية التعقيدات على طول O(N) (على إراتوستينس) ، O(N/log(log(N))) (على أتكن) لا نستطيع أن نقول (الصغيرة N=10_000) أي خوارزمية إذا تم تنفيذها سوف يكون أسرع.
أكيم Flammenkamp كتب في غربال إراتوستينس:
ذكرها:
@num1
على فترات أكبر عن 10^9, بالتأكيد لأولئك > 10^10, غربال إراتوستينس هو تفوقت قبل غربال اتكينز و بيرنشتاين الذي يستخدم غير القابل للاختزال ثنائي الدرجة الثانية أشكال.انظر ورقة خلفية المعلومات وكذلك الفقرة 5 من W.غالواي دكتوراهأطروحة.
ولذلك 10_000 غربال إراتوستينس يمكن أن يكون أسرع إذا غربال آتكن.
للرد على العملية التعليمة البرمجية prime_sieve.ج (ذكرها num1)
باستخدام GMP, يمكن أن تكون ما يلي:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
على 2.33 GHz ماك بوك برو ، فإنه ينفذ على النحو التالي:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
حساب 1,000,000 يعبي على نفس الكمبيوتر المحمول:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP هو الأمثل للغاية لهذا النوع من الشيء.إلا إذا كنت تريد حقا أن نفهم خوارزميات طريق الكتابة الخاصة بك ستكون ينصح باستخدام libGMP تحت C.
ليست فعالة على الإطلاق, ولكن يمكنك استخدام التعبير العادي لاختبار الأعداد الأولية.
/^1?$|^(11+?)\1+$/
هذه الاختبارات إذا ، عن سلسلة تتكون من k “1"s ، k هو وليس رئيس الوزراء (أيإذا كانت السلسلة تتكون من واحد "1"أو أي عدد من "1"s التي يمكن التعبير عنها كما n-ary المنتج).
لقد تكيفت رمز الاطلاع على CodeProject لخلق التالية:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
الاختبار هذا ASP.NET خادم أخذت rountine حوالي 1 دقيقة إلى تشغيل.
هنا هو غربال إراتوستينس التي كتبت في PowerShell قبل بضعة أيام.وقد المعلمة لتحديد عدد الأعداد الأولية التي يجب أن تعاد.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
غربال إراتوستينس هو الطريق للذهاب ، بسبب انها البساطة والسرعة.تنفيذ بلدي في ج
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
الوقت وحدة المعالجة المركزية لإيجاد الأعداد الأولية (على بنتيوم ثنائي النواة E2140 1.6 GHz باستخدام جوهر واحد)
~ 4s ليم = 100,000,000
تكييف وبعد يوم من GateKiller, ها هي النسخة النهائية التي كنت تستخدم.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
هو في الأساس نفسه ، ولكني وأضاف "كسر على الجذر التربيعي" اقتراح تغيير بعض المتغيرات حول لجعلها تناسب على نحو أفضل بالنسبة لي.(كنت أعمل على يولر حاجة 10001th رئيس الوزراء)
غربال يبدو أن إجابة خاطئة.غربال يعطيك يعبي حتى عدد N, لا أولا N يعبي.تشغيل @عمران أو @أندرو Szeto ، يعبي حتى N.
غربال قد تكون لا تزال قابلة للاستخدام إذا كنت تحاول أن تبقي المناخل تزداد أعداد أكبر حتى تصل إلى حجم معين من مجموعة النتائج ، واستخدام بعض التخزين المؤقت من الأرقام التي تم الحصول عليها بالفعل ، ولكن أعتقد أنه سوف يكون لا يزال أسرع من الحل مثل @بات.
في بيثون
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
على deque غربال خوارزمية ذكرها BenGoldberg يستحق نظرة فاحصة ، ليس فقط لأنه هو أنيق جدا ولكن أيضا لأنه يمكن في بعض الأحيان تكون مفيدة في الممارسة (على عكس غربال آتكن الذي هو محض الأكاديمية ممارسة الرياضة).
الفكرة الأساسية وراء deque غربال الخوارزمية هو استخدام صغيرة انزلاق غربال فقط كبيرة بما يكفي لاحتواء واحد على الأقل منفصلة متعددة لكل حاليا 'النشط' العوامل الرئيسية - أيتلك يعبي الذين مربع لا يتجاوز به أدنى العدد حاليا ممثلة تتحرك غربال.فرق آخر أن الشركات المملوكة للدولة هو أن deque غربال المتاجر الفعلية العوامل في فتحات من المركبة ، غير المنطقية.
الخوارزمية يمتد حجم غربال نافذة حسب الحاجة ، مما أدى إلى حد ما حتى الأداء على نطاق واسع حتى غربال يبدأ تتجاوز قدرة وحدة المعالجة المركزية L1 cache بشكل ملحوظ.آخر رئيس الوزراء الذي يناسب تماما هو 25,237,523 (إن 1,579,791 st رئيس الوزراء) الذي يعطي الخام الملعب الرقم معقول نطاق التشغيل من الخوارزمية.
خوارزمية بسيطة وقوية ، حتى الأداء على مجموعة أوسع بكثير من unsegmented غربال إراتوستينس.وهذا الأخير هو أسرع كثيرا طالما لها غربال يناسب تماما في ذاكرة التخزين المؤقت ، أيتصل إلى 2^16 الصعاب فقط غربال مع بايت الحجم bools.ثم أدائها قطرات أكثر وأكثر ، على الرغم من أنه يبقى دائما أسرع بكثير من deque على الرغم من الإعاقة (على الأقل في ترجمة لغات مثل C/C++, Pascal أو Java/C#).
هنا هو تقديم deque غربال الخوارزمية في C#, لأنني أجد أن اللغة - على الرغم من العديد من العيوب - أكثر عملية بالنسبة النماذج والخوارزميات والتجريب من أسمى مرهقة متحذلق C++. (وي:أنا باستخدام مجانا LINQPad مما يجعل من الممكن أن الغوص في الحق دون كل النقائص مع إعداد مشاريع makefiles الدلائل أو غيرها ، وأنه يعطي لي نفس الدرجة من التفاعل كما الثعبان موجه).
C# لا يكون صريح deque نوع لكن عادي List<int> يعمل بشكل جيد بما فيه الكفاية لإثبات الخوارزمية.
ملاحظة:هذا الإصدار لا يستخدم deque عن يعبي, لأنه ببساطة لا معنى البوب الجذر التربيعي(ن) من ن يعبي.ما فائدة أن إزالة 100 يعبي وترك 9900?على الأقل بهذه الطريقة كل يعبي يتم جمعها في أنيق ناقلات ، وعلى استعداد لمزيد من المعالجة.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
وهنا اثنين من وظائف المساعد:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
ربما أسهل طريقة فهم الخوارزمية هو تصور على أنها خاصة مجزأة غربال إراتوستينس مع شريحة حجم 1 ، يرافقه تجاوز المنطقة حيث يعبي تأتي للراحة عندما تبادل لاطلاق النار على نهاية الجزء.إلا أن خلية واحدة من الجزء (أ.ك.أ. sieve[0]) وقد تم بالفعل منخول عندما نصل إلى ذلك ، لأنه دهس في حين كان جزء من تجاوز المنطقة.
الرقم الذي يمثله sieve[0] يقام في sieve_base, ، على الرغم من sieve_front أو window_base كما سيكون جيد الأسماء التي تسمح أن أوجه التشابه بين كود أو تطبيقات مجزأة/إطارات المناخل.
إذا sieve[0] يحتوي على قيمة غير صفرية ثم أن قيمة عامل sieve_base, والتي يمكن بالتالي أن تكون معترف بها باعتبارها مركب.منذ الخليوي 0 متعددة من هذا العامل فمن السهل لحساب المقبل هوب, وهو ببساطة 0 بالإضافة إلى أن عامل.يجب أن الخلية المحتلة بالفعل من قبل عامل آخر ثم نحن ببساطة إضافة عامل مرة أخرى وهكذا حتى نجد متعددة من العامل حيث لا يوجد عامل آخر متوقفة حاليا (تمديد غربال إذا لزم الأمر).وهذا يعني أيضا أن هناك حاجة لتخزين العمل الحالية إزاحة مختلف يعبي من شريحة واحدة إلى أخرى ، كما في الطبيعي مجزأة غربال.كلما وجدنا عاملا في sieve[0], ، العمل الحالية في تعويض 0.
ورئيس الوزراء الحالي يأتي في اللعب بالطريقة التالية.رئيس الوزراء فقط يمكن أن تصبح الحالي بعد الخاصة التواجد في تيار (أيعندما تم الكشف عن رئيس الوزراء ، لأنه لم يتم وضع علامة مع عامل) ، وسوف تظل الحالي حتى اللحظة أن sieve[0] تصل إلى متر.كل أقل مضاعفات هذا رئيس الوزراء يجب أن يكون قد ضرب قبالة بسبب أنشطة أصغر يعبي مثل العادي الشركات المملوكة للدولة.ولكن أيا من أصغر يعبي يمكن أن يضرب قبالة ساحة ، لأن العامل الوحيد في الساحة هو رئيس الوزراء نفسه لم يكن بعد في الدورة الدموية في هذه المرحلة.هذا ما يفسر الإجراءات التي اتخذتها الخوارزمية في حالة sieve_base == current_prime_squared (مما يعني sieve[0] == 0, بالمناسبة).
الآن القضية sieve[0] == 0 && sieve_base < current_prime_squared وأوضح بسهولة:فهذا يعني أن sieve_base لا يمكن أن تكون متعددة من أي من الأعداد الأولية الأصغر من رئيس الوزراء الحالي ، وإلا فإنه قد تم وضع علامة عليها باعتبارها مركب.أنا لا يمكن أن يكون أعلى متعددة من رئيس الوزراء الحالي إما لأن قيمته أقل من رئيس الوزراء الحالي مربع.ومن ثم فإنه يجب أن يكون رئيس الوزراء الجديد.
الخوارزمية من الواضح مستوحاة من غربال إراتوستينس ، ولكن أيضا من الواضح أنها مختلفة جدا.غربال إراتوستينس يستمد سرعة فائقة من بساطة العمليات الأولية:واحد مؤشر إضافة مخزن واحد لكل خطوة من العملية هو أنه لا لفترات طويلة من الوقت.
هنا هو بسيط ، unsegmented غربال إراتوستينس أنا عادة استخدام النخل العامل يعبي في ushort مجموعة ، أيتصل إلى 2^16.من أجل هذا المنصب لقد عدلت إلى العمل بعد 2^16 عن طريق استبدال int بالنسبة ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
عندما النخل أول 10000 يعبي نموذجية L1 cache 32 KiByte سيتم تجاوز ولكن وظيفة لا يزال سريع جدا (جزء من الألف من الثانية حتى في C#).
إذا قارنت هذا الرمز إلى deque غربال ثم فمن السهل أن نرى أن عمليات deque غربال أكثر تعقيدا, وأنه لا يمكن على نحو فعال amortise النفقات العامة لأنه دائما أقصر وقت ممكن تمتد من المعابر في صف واحد (واحد بالضبط معبر واحد ، بعد تخطي كل المضاعفات التي قد تم شطبها بالفعل).
ملاحظة:C# كود يستخدم int بدلا من uint لأن أحدث المجمعين لديهم عادة توليد رمز المستوى المطلوب uint, ربما من أجل دفع الناس نحو توقيع الصحيحه...في C++ الإصدار من رمز أعلاه اعتدت unsigned جميع الطبيعي ؛ المعيار قد يكون في C++ لأنني أردت أن يستند يفترض أنها كافية deque نوع (std::deque<unsigned>;لم يكن هناك أي كسب الأداء من استخدام unsigned short).هنا هي أرقام بلدي هاسويل الكمبيوتر المحمول (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
ملاحظة:C# الأوقات بالضبط مزدوجة C++ التوقيت ، وهو أمر جيد جدا بالنسبة C# و ìt يدل على أن List<int> ولا ترهل حتى لو أساء كما deque.
بسيطة غربال رمز لا يزال ضربات deque من الماء ، على الرغم من أنها تعمل بالفعل خارج العمل العادية مجموعة (L1 حجم ذاكرة التخزين المؤقت تجاوز بنسبة 50%, مع ما يصاحب ذلك من ذاكرة التخزين المؤقت سحق).هو الجزء المسيطر هنا هو القراءة من منخول يعبي و هذا لا يتأثر بكثير من المشكلة ذاكرة التخزين المؤقت.في أي حال من وظيفة مصممة النخل العوامل من العوامل ، أيالمستوى 0 في المستوى 3 غربال الهرمي ، و عادة لديها للعودة سوى بضع مئات من العوامل أو عدد قليل من آلاف.وبالتالي بساطته.
يمكن تحسين أداء أكثر من أمر من حجم باستخدام مجزأة غربال وتحسين رمز استخراج منخول يعبي (صعدت وزارة الدفاع 3 و بسطه مرتين أو وزارة الدفاع 15 و بسطه مرة واحدة) و بعد المزيد من الأداء يمكن أن تقلص من التعليمات البرمجية باستخدام 16 وزارة الدفاع أو وزارة الدفاع 30 عجلة مع كل الزركشة (أيكامل الفتح لجميع المخلفات).شيء من هذا القبيل هو موضح في جوابي العثور على رئيس الوزراء وضع عدد الوزراء على مراجعة التعليمات البرمجية ، حيث مشكلة مماثلة تم مناقشته.ولكن من الصعب أن نرى نقطة في تحسين الفرعية ميلي ثانية واحدة مرة واحدة مهمة...
لوضع الامور في نصابها ، وهنا C++ أوقات النخل تصل إلى 100,000,000:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
وعلى النقيض من ذلك ، مجزأة غربال في C# مع عدد قليل من أجراس وصفارات يقوم بنفس العمل في 95 ms (أي C++ الأوقات المتاحة ، منذ أن أفعل رمز التحديات فقط في C# في هذه اللحظة).
الأمور قد تبدو مختلفة بالتأكيد في تفسير اللغة مثل الثعبان حيث كل عملية ثقيل تكلفة مترجم النفقات العامة الأقزام جميع الخلافات بسبب توقع مقابلmispredicted فروع أو الفرعية دورة العمليات (التحول ، إضافة) مقابلمتعدد دورة العمليات (الضرب, وربما شعبة).التي لا بد أن يؤدي إلى تآكل بساطة الاستفادة من غربال إراتوستينس, و هذا يمكن أن يجعل deque الحل قليلا أكثر جاذبية.
أيضا الكثير من الأوقات ذكرت من قبل الآخرين المشاركين في هذا الموضوع ربما يسيطر عليها وقت الإخراج.إنها حرب مختلفة تماما حيث كان السلاح الرئيسي هو فئة بسيطة مثل هذه:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
أن يأخذ أقل من 1 مللي ثانية للكتابة 10000 (فرز) أرقام.انها فئة ثابتة لأن المقصود هو نصية إدراجها في الترميز التحدي المقدمة ، مع الحد الأدنى من الجلبة و صفر النفقات العامة.
بشكل عام وجدت أن يكون كثيرا أسرع إذا ركزت يتم العمل على كامل دفعات ، معنى غربال طائفة معينة ، ثم استخراج كافة يعبي في ناقلات/مجموعة ، ثم الانفجار كل مجموعة ، ثم غربال المقبل مجموعة وهلم جرا ، بدلا من اختلاط كل شيء معا.وجود مهام منفصلة تركز على مهام محددة أيضا يجعل من الأسهل إلى مزيج المباراة ، فإنه يمكن إعادة استخدامها ، كما أنه يخفف التنمية/اختبار.
هنا هو بلدي VB 2008 الرمز ، الذي يجد كل يعبي <10,000,000 في 1 دقيقة 27 ثانية على جهاز الكمبيوتر المحمول العمل.يتخطى حتى أرقام فقط يبحث عن الأعداد الأولية التي هي < إن الجذر التربيعي الاختبار عدد.وهي مصممة فقط للعثور على الأعداد من 0 إلى بمشروع رصد قيمة.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
التالية Mathcad رمز احتساب أول مليون يعبي في أقل من 3 دقائق.
نضع في اعتبارنا أن هذا سيكون باستخدام النقطة العائمة الزوجي لجميع الأرقام هي الأساس تفسيرها.أتمنى أن تكون الجملة واضحة.
هنا هو C++ الحل باستخدام نموذج من الشركات المملوكة للدولة:
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
علما أن هذا الإصدار من غربال يمكن حساب يعبي إلى أجل غير مسمى.
نلاحظ أيضا في المحكمة الخاصة بلبنان deque يأخذ O(1) الوقت لأداء push_back, pop_front, و الوصول العشوائي على الرغم من subscripting.
على resize تستغرق العملية O(n) الوقت ، حيث n هو عدد العناصر التي يتم إضافتها.بسبب كيفية استخدام هذه الدالة يمكننا علاج هذه صغيرة ثابتة.
الجسم من while حلقة في my_insert يتم تنفيذ O(log log n) مرات, حيث n يساوي المتغير maybe_prime.لأن هذا هو الشرط التعبير while سوف تقيم صحيح مرة واحدة لكل عنصر من maybe_prime.انظر "المقسوم وظيفة"في ويكيبيديا.
ضرب من قبل عدد من المرات my_insert يسمى يدل على أنه ينبغي أن تأخذ O(n log log n) الوقت إلى قائمة n يعبي...وهو غير المستغرب أن تعقيد الوقت الذي غربال إراتوستينس من المفترض أن يكون.
ومع ذلك ، في حين أن هذا الرمز هو كفاءة ليس الأكثر كفاءة...أود أن أقترح بشدة باستخدام مكتبة متخصصة يعبي الجيل ، مثل primesieve.أي فعالة حقا, حسنا الحل الأمثل ، وسوف تتخذ المزيد من التعليمات البرمجية من أي شخص يريد أن اكتب في ستاكوفيرفلوو.
باستخدام غربال إراتوستينس ، وحساب جدا بشكل أسرع مقارنة "معروف" على نطاق الأعداد الخوارزمية.
باستخدام شبة الكود من ويكي (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) انا تكون قادرة على أن يكون الحل في C#.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) يأخذ 2s و 330ms.
ملاحظة:القيمة قد تختلف تعتمد على مواصفات الأجهزة.
أقضي بعض الوقت في كتابة برنامج حساب الكثير من يعبي و هذا هو رمز اعتدت على حساب ملف نصي يحتوي على أول 1.000.000.000 يعبي.إنه في الألمانية ، ولكن الجزء المثير للاهتمام هو طريقة calcPrimes().الأعداد الأولية المخزنة في صفيف يسمى Primzahlen.أوصي 64 بت وحدة المعالجة المركزية لأن الحسابات مع 64bit الاعداد الصحيحه.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
كنت قد كتبت هذا باستخدام بيثون ، كما بدأت للتو تعلم أنه يعمل بشكل جيد تماما.10000 ال رئيس تولد عن طريق هذا الرمز نفسه كما ذكر في http://primes.utm.edu/lists/small/10000.txt.للتحقق مما إذا n هو رئيس الوزراء أم لا ، تقسيم n من خلال الأرقام من 2 إلى sqrt(n).إذا كان أي من هذه المجموعة من عدد تماما يقسم n ثم إنه ليس رئيس الوزراء.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
لقد تم العمل على إيجاد يعبي لمدة عام.هذا هو ما وجدته أن تكون أسرع:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 نانو ثانية للوصول إلى 2147483629 ابتداء من الساعة 2.
هنا هو بلدي رمز الذي يجد
أول 10000 يعبي في 0.049655 ثانية على جهاز الكمبيوتر المحمول ، أول 1,000,000 يعبي في أقل من 6 ثوان الأولى 2,000,000 في 15 ثانية
تفسير قليلا.يستخدم هذا الأسلوب 2 التقنيات للعثور على عدد الوزراء
- أولا وقبل كل شيء أي من غير عدد الوزراء هو مركب من مضاعفات الأعداد حتى هذا الرمز اختبار بقسمة اختبار عدد من أصغر الأعداد بدلا من أي عدد ، وهذا يقلل من حساب من قبل على الأقل 10 مرات عن عدد 4 أرقام و أكثر لعدد أكبر
- ثانيا إلى جانب تقسيم من قبل رئيس الوزراء ، إلا أنه يقسم من الأعداد الأولية التي هي أصغر أو يساوي جذر رقم يجري اختبارها وكذلك الحد من الحسابات إلى حد كبير ، يعمل هذا لأن أي عدد أكبر من عدد الجذور سوف يكون نظيره الرقم الذي يجب أن يكون أصغر من عدد الجذور ولكن بما أننا اختبرنا جميع أرقام أصغر من الجذر بالفعل, لذلك لا تحتاج إلى عناء مع عدد أكبر من عدد الجذور التي يجري اختبارها.
إخراج نموذج لأول 10,000 عدد الوزراء
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
هنا هو رمز في لغة C ،
أدخل 1 ثم 10 ، 000 إلى طباعة أول 10000 يعبي.
تحرير:لقد نسيت هذا يحتوي على مكتبة الرياضيات ,إذا كنت على ويندوز أو visual studio من ذلك ينبغي أن يكون على ما يرام ولكن على لينكس يجب ترجمة التعليمات البرمجية باستخدام -lm حجة أو قد لا تعمل التعليمات البرمجية
على سبيل المثال:دول مجلس التعاون الخليجي -الجدار -o "e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
هنا التعليمات البرمجية التي صنعت :
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
باستخدام مجموعة.النموذج الأولي.طريقة البحث() في جافا سكريبت.2214.486 ms
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
أستطيع أن أعطي لكم بعض النصائح التي عليك تنفيذها.
- لكل رقم ، الحصول على نصف هذا العدد.E. g.لفحص 21, فقط الحصول على ما تبقى بتقسيمه من مجموعة 2-10.
- إذا كان عدد فردي فقط القسمة على عدد فردي ، والعكس بالعكس.مثل 21, تقسيم 3, 5, 7, 9 فقط.
الطريقة الأكثر فعالية استيقظت حتى الآن.
منذ كنت تريد الأولى 10000 يعبي فقط بدلا من الترميز خوارزمية معقدة أنا أقترح التالية
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
الكلمة الآن هو رئيس الوزراء كما كنت في حاجة إليها
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
