برنامج للعثور على أرقام رئيسية
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أريد أن أجد الرقم الرئيسي بين 0 ومتغير طويل لكنني غير قادر على الحصول على أي إخراج.
البرنامج هو
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
هل يمكن لأي شخص مساعدتي وإيجاد الخطأ المحتمل في البرنامج؟
المحلول
يمكنك القيام بذلك بشكل أسرع باستخدام تقريبا الأمثل غربال شعبة المحاكمة في خط واحد (طويل) مثل هذا:
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
صيغة التقريب لعدد الأعداد الأولية المستخدمة هنا هي π(x) < 1.26 x / ln(x). وبعد نحن بحاجة فقط إلى الاختبار من قبل الأعداد الأولية ليست أكبر من x = sqrt(num).
نلاحظ أن غربال eratosthenes. يحتوي على تعقيد وقت التشغيل أفضل بكثير من تقسيم التجربة (يجب أن يعمل بشكل أسرع بكثير num القيم، عند تنفيذها بشكل صحيح).
نصائح أخرى
جرب هذا:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
تحتاج فقط إلى التحقق من الطبقات الفردية حتى الجذر التربيعي للرقم. وبعبارة أخرى تحتاج حلقة الداخلية الخاصة بك إلى البدء:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
يمكنك أيضا الخروج من الدالة بمجرد أن تجد الرقم ليس رئيسا، لا تحتاج إلى التحقق من أي مقسمات أخرى (أرى أنك تفعل ذلك بالفعل!).
هذا سوف يعمل فقط إذا كان عدد أكبر من اثنين.
لا SQRT.
يمكنك تجنب SQRT تماما عن طريق الحفاظ على مبلغ قيد التشغيل. علي سبيل المثال:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
وذلك لأن مجموع الأرقام 1+ (3 + 5) + (7 + 9) سوف يمنحك سلسلة من المربعات الفردية (1،9،25 وما إلى ذلك). وبالتالي j يمثل الجذر التربيعي لل square_sum. وبعد طالما square_sum اقل من i ومن بعد j أقل من الجذر التربيعي.
ذكر الناس بضعة لبنات بناء نحو القيام بذلك بكفاءة، لكن لا أحد يضع القطع معا. ال غربال eratosthenes. هي بداية جيدة، ولكن مع ذلك سوف تنفد من الذاكرة طويل قبل أن تصل إلى الحد الأقصى الذي قمت بتعيينه. هذا لا يعني أنه عديم الفائدة رغم ذلك - عند قيامك في حلقةك، ما تهتم به حقا مقصورات. على هذا النحو، يمكنك البدء باستخدام المنخل لإنشاء قاعدة من المقسومات Prime، ثم استخدم تلك الموجودة في الحلقة لاختبار أرقام الأولية.
عندما تكتب الحلقة، إلا أنك حقا لا ترغب في الولايات المتحدة SQRT (I) في حالة الحلقة كما اقترح إجابات. أنت وأنا أعلم أن SQRT هي وظيفة "نقية" تعطي دائما نفس الإجابة إذا أعطيت نفس معلمة الإدخال. لسوء الحظ، لا يعرف المحول البرمجي أنه، لذلك إذا استخدم شيء مثل "<= math.sqrt (x)" في حالة الحلقة، فسوف يعيد حساب SQRT من الرقم كل تكرار من الحلقة.
يمكنك تجنب ذلك بضع طرق مختلفة. يمكنك إما حساب SQRT مسبقا قبل الحلقة، واستخدم القيمة المحسنة مسبقا في حالة الحلقة، أو يمكنك العمل في الاتجاه الآخر، وتغيير i<Math.sqrt(x) ل i*i<x. وبعد شخصيا، أود مسبقا حساب الجذر التربيعي - أعتقد أنه أكثر وضوحا وربما أسرع قليلا - ولكن هذا يعتمد على عدد تكرارات الحلقة ( i*i يعني أنه لا يزال يقوم بالضرب في الحلقة). مع بعض التكرارات فقط، i*i سيكون عادة أسرع. مع ما يكفي من التكرارات، وفقدان i*i كل التكرار تفوق وقت التنفيذ sqrt مرة واحدة خارج الحلقة.
ربما يكون هذا كافيا لحجم الأرقام التي تتعامل معها - أي حد 15 أرقام يعني أن الجذر التربيعي هو 7 أو 8 أرقام، والتي تناسبها كمية معقولة جدا من الذاكرة. من ناحية أخرى، إذا كنت ترغب في التعامل مع الأرقام في هذا النطاق كثيرا، فقد ترغب في إلقاء نظرة على بعض خوارزميات الفحص الرئيسية الأكثر تطورا، مثل خوارزميات بولارد أو برنت. وبعد هذه هي أكثر تعقيدا (لوضعها أقل ما يقال) ولكن كثيرا أسرع لأرقام كبيرة.
هناك خوارزميات أخرى لأرقام أكبر (الغربال التربيعي, الحقل رقم عام) لكننا لن ندخلهم في الوقت الحالي - إنهم أكثر تعقيدا للغاية، ومفيدة حقا فقط للتعامل مع أرقام كبيرة حقا (يبدأ GNFS في النطاق المكون من 100+).
الخطوة الأولى: اكتب طريقة تمديد لمعرفة ما إذا كانت المدخلات رئيسا
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 خطوة: اكتب الطريقة التي سطبع جميع الأرقام الرئيسية التي تتراوح بين 0 وعدد الإدخال
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
قد يكون فقط رأيي، ولكن هناك خطأ خطير آخر في البرنامج (إعداد سؤال "Prime" المعطى، الذي تم إجابته بدقة).
مثل بقية المستجيبين، أفترض أن هذه هي الواجبات المنزلية، والتي تشير إلى أنك تريد أن تصبح مطورا (يفترض).
تحتاج إلى تعلم كيفية تقليص التعليمات البرمجية الخاصة بك. إنه ليس شيئا ستحتاج إليه دائما في مشروع، لكن من الجيد معرفة كيفية القيام بذلك.
طريقة Prime_Num (Long Num) قد تقف بشكل أفضل وأكثر وصفية. وإذا كان من المفترض أن تجد جميع الأرقام الأولية أقل من رقم معين، يجب أن تعيدهم كقائمة. هذا يجعل من السهل فصل الشاشة ووظائفك.
إذا أعادت ببساطة إيليست تحتوي على أرقام أولى، فيمكنك عرضها في وظيفتك الرئيسية (ربما تتصل بوظيفة خارجية أخرى إلى طباعةها بشكل جميل) أو استخدمها في عمليات حسابات أخرى أسفل الخط.
لذلك أفضل توصيتي لك هي أن تفعل شيئا مثل هذا:
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
حتى لو انتهى الأمر بالعمل في مكان ما، فلن تكون هناك حاجة إلى تعراب مثل هذه، من الجيد معرفة كيفية القيام بذلك.
EDIT_ADD: إذا تم تصحيح NESS هذا الغرض من السؤال هو فقط إخراج دفق مستمر من الأعداد الأولية طالما يتم تشغيل البرنامج (الضغط على الإيقاف المؤقت / الاستراحة للتوقف مؤقتا وأي مفتاح للبدء من جديد) مع عدم وجود أمل خطير في كل الوصول إلى هذا الجزء العلوي حدد، ثم يجب كتابة التعليمات البرمجية مع عدم وجود حجة الحد الأعلى وشيك مجموعة من "صحيح" لأول 'i' للحلقة. من ناحية أخرى، إذا كان السؤال مطلوبا بالفعل طباعة الأعداد الأولية حتى الحد الأقصى، فسيقوم التعليمة البرمجية التالية بإجراء المهمة بشكل أكثر كفاءة باستخدام تقسيم التجربة فقط للأرقام الفردية، مع ميزة أنها لا تستخدم الذاكرة على الإطلاق (يمكن تحويله أيضا إلى حلقة مستمرة حسب ما سبق):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
أولا، لا ينتج قانون السؤال أي إخراج بسبب وجود متغيرات حلقة الأعداد الصحيحة والحد المختبر هو عدد صحيح طويل ضخم، مما يعني أنه من المستحيل أن تصل الحلقة إلى الحد الأدنى من حلقة داخلية تحرير: حيث توجد حلقات "J" المتغير إلى الأرقام السالبة؛ عندما يعود "J" المتغير إلى -1، يفشل رقم اختباره في الاختبار الرئيسي لأن جميع الأرقام قابلة للقسمة بالتساوي بواسطة -1 end_edit.. وبعد حتى إذا تم تصحيح هذا، فإن رمز السؤال ينتج إخراج بطيئا للغاية لأنه يحصل على أقسام 64 بت من الكميات الكبيرة جدا من الأرقام المركبة (جميع الأرقام الزائد بالإضافة إلى المركب الغريب) من النطاق بالكامل من الأرقام حتى هذا أعلى عدد العشرة المرفوعة إلى السلطة السادسة عشرة لكل ما يمكن أن ينتج عنه. يعمل الرمز أعلاه لأنه يحد من الحساب إلى الأرقام الفردية فقط ولا يقوم إلا بتقسيمات modulo تصل إلى الجذر التربيعي من الرقم الحالي الذي يتم اختباره.
يستغرق ذلك ساعة أو نحو ذلك لعرض الأعوام التي تصل إلى مليار ما يصل إلى مليار، لذلك يمكن للمرء أن يتخيل مقدار الوقت الذي سيستغرقه لإظهار جميع الأعداد الأولية إلى عشرة آلاف تريليون (10 مرفوعة إلى السلطة السادسة عشرة)، خاصة وأن الحساب يبطأ مع زيادة النطاق. end_edit_add.
على الرغم من أن Liner One (نوع) الإجابة بواسطة Slaks باستخدام LinQ Works، إلا أنها ليست غربال eratosthenes كما هي مجرد نسخة غير مخطثة من قسم التجربة, ، لا يبدأ عدم تخفيفه في أنه لا يلغي الأعداد الأولية الفردية، ولا يبدأ في مربع قاعدة الأساس الموجودة، ولا يتوقف عن إعدامه للعميل الأولية أكبر من الجذر التربيعي للعدد العلوي للحرب. كما أنها بطيئة جدا بسبب عمليات التعداد المتعددة المتداخلة.
إنه في الواقع إساءة استخدام الأسلوب الإجمالي ل LINQ ولا يستخدم بفعالية أول منتجين من مجموعة LINQ. يمكن أن تصبح تقسيما محاكمة محسنة بأقل تعداد النفقات العامة على النحو التالي:
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
الذي يعمل عدة مرات أسرع من إجابة Slaks. ومع ذلك، فإنه لا يزال بطيئا والذاكرة مكثفة بسبب توليد القائمة والمعدادات المتعددة وكذلك الفجوة المتعددة (ضمنية بواسطة العمليات المعدلة).
يعمل المنخل الحقيقي التالي لتنفيذ EriatoSthenes بشكل أسرع حوالي 30 مرة ويستغرق الذاكرة أقل بكثير لأنها تستخدم فقط تمثيل واحد فقط لكل رقم، وتحد من تعداده إلى إخراج تسلسل المؤتمر النهائي، بالإضافة إلى تحسينات التعامل مع المركبات الفردية فقط، وعلى الإعدام فقط من مربعات الأعداد الأولية الأساسية للأعميل الأولية حتى الجذر التربيعي للحد الأقصى للرقم، كما يلي:
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
يحسب الرمز أعلاه جميع الأعداد الأولية إلى عشرة ملايين نطاق في حوالي 77 مللي ثانية على إنتل I7-2700K (3.5 جيجا هرتز).
يمكن استدعاء أي من الأساليب الثابتة واختبارها ببيانات باستخدام الطريقة الرئيسية الثابتة كما يلي:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
والتي ستظهر عدد الأعداد الأولية في التسلسل حتى الحد الأقصى، وجدت آخر رئيسا، والوقت المنفق في تعداد ذلك بعيد.
EDIT_ADD: ومع ذلك، من أجل إنتاج تعداد عدد الأعداد الأولية أقل من عشرة آلاف تريليون تريليون (عشرة إلى القوة السادسة عشرة) حيث يسأل السؤال، هناك حاجة إلى نهج مقدم من الصفحات المخدرية باستخدام المعالجة متعددة النواة ولكن حتى مع C ++ و الأمثل للغاية primesieve, وهذا يتطلب شيئا أكثر من 400 ساعة فقط لإنتاج عدد الأعداد الأولية الموجودة، وعمل عشرات المرات التي تتطلع إلى تعداد كل منهم أكثر من عام للقيام بما يسأله السؤال. للقيام بذلك باستخدام خوارزمية قسم التجريبية غير المحسنة غير المسموح بها حاولت، سيستغرق الأمر سوبر إيونس وقم بوقت طويل جدا حتى باستخدام خوارزمية تقسيم تجريبية محسنة كما في شيء مثل عشرة لسنوات قوة المليونثين (أيهما مليون زيروس !! !).
لا عجب كثيرا أن جهاز سطح المكتب جلس فقط واستوقف عندما جربه !!!! إذا كان قد جرب مجموعة أصغر مثل مليون شخص، فسيظل كان سيوجه أنه يأخذ في نطاق الثواني كما هو موضح.
لن يقطع الحلول التي أشرتها هنا إما حتى في الغربال الأخير من eratosthenes واحد سيتطلب حوالي 640 terabytes من الذاكرة لهذا النطاق.
هذا هو السبب في أن مجرد نهج مقطوع للصفحة مثل مرحلة الأولية يمكنه التعامل مع هذا النوع من المشكلة للنطاق كما هو محدد على الإطلاق، وحتى يتطلب وقتا طويلا جدا، كما في أسابيع إلى سنوات إلا إذا كان أحد لديه إمكانية الوصول إلى كمبيوتر سوبر مئات الآلاف من النوى. end_edit_add.
تنبعث منها مثل المزيد من الواجبات المنزلية. حاسبة الرسوم البيانية القديمة جدا لديها برنامج رئيسي مثل هذا. من الناحية الفنية، يحتاج حلقة فحص الدخل الداخلي فقط إلى الركض إلى I ^ (1/2). هل تحتاج إلى العثور على "كل" الأرقام الأولية بين 0 و L؟ المشكلة الرئيسية الأخرى هي أن متغيرات حلقة الخاص بك هي "int" في حين أن بيانات الإدخال الخاصة بك هي "طويلة"، فسيؤدي ذلك إلى فشل سعة تجعل حلقاتك تفشل في تنفيذها مرة واحدة. إصلاح متغيرات الحلقة.
رمز سطر واحد في C #: -
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
ال غربال eratosthenes. الإجابة أعلاه ليست صحيحة تماما. كما هو مكتوب ستجد جميع الأعداد الأولية بين 1 و 1000000. للعثور على جميع الأعداد الأولية بين 1 والرقم استخدام:
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
يجب أن يكون SEED of the Aggrogate 1 إلى الأسطوانات لأن هذه القائمة ستتضمن القائمة النهائية للقرأ. ال Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) هو عدد المرات التي يتم فيها تطهير البذور.
منتديات البورصة استمتع بتطبيق وحدة التحكم الجيدة المدرجة التي تتطلع إلى الكتابة التي تم العثور عليها في الأعداد الأولية إلى ملف، يبدو أنه يمكنك أيضا استخدام هذا الملف نفسه كنقطة انطلاق حتى لا تضطر إلى إعادة تشغيل العثور على القراءة من 2، وهي توفر تنزيلا لهذا الملف مع كل ما وجدما أعيابا يصل إلى 100 مليون حتى ستكون بداية جيدة.
تأخذ الخوارزمية في الصفحة أيضا اختصارات زوجين (أرقام فردية وفحصها فقط إلى الجذر المربع) مما يجعلها فعالة للغاية وسوف يسمح لك بحساب أرقام طويلة.
لذلك هذا هو أساسا فقط اثنين من الصور, ، واحد، والأكثر سوءا، for (int j = 2; j <= num; j++) وهو سبب الاختبار غير المنتج 1%2,1%3 ... 1%(10^15-1) الذي يمضي لفترة طويلة جدا حتى لا يحصل المرجع "أي إخراج". يجب أن يكون ذلك j < i; في حين أن. الآخر، طفيفة في المقارنة، هو ذلك i يجب أن تبدأ من 2 وليس من 0:
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
بالتأكيد لا يمكن توقعه بشكل معقول وحدة طباعة من 28 تريليونات الأعداد الأولية أو نحو ذلك لإكمالها في أي إطار زمني معقول. لذلك، كان النية الأصلية للمشكلة من الواضح طباعة دفق ثابت من الأعداد الأولية، إلى أجل غير مسمى. وبعد وبالتالي كل الحلول التي تقترح الاستخدام البسيط من غربال eratosthenes هي تماما دون الجدارة هنا، ل بسيط من غربال eratosthenes يحدها - يجب تحديد حد مسبقا.
ما يمكن أن يعمل هنا هو شعبة التجربة الأمثل التي من شأنها أن تنقذ الأعداد الأولية لأنها تجدها، واختبارها من الأعداد الأولية، وليس فقط جميع الأرقام أدناه المرشح.
البديل الثاني، مع تعقيد أفضل بكثير (أي أسرع بكثير) هو استخدام غربال مجزأة من eratosthenes. وبعد وهو متزايد وغير محدود.
سيستخدم كلا الخططين إنتاج مزدوج من الأعداد الأولية: واحد من شأنه إنتاج وحفظ الأعداد الأولية، لاستخدامها من قبل المرحلة الأخرى في الاختبار (أو النافذة)، أعلى بكثير من الحد الأقصى للمرحلة الأولى (أسفل مراحلها بالطبع - تمديد المرحلة الأولى تلقائيا، كما ستذهب المرحلة الثانية كذلك وأكثر صعودا).
أن تكون صريحا تماما، بعض الحلول المقترحة بطيئة حقا، وبالتالي فهي اقتراحات سيئة. لاختبار رقم واحد ليكون رئيسيا، تحتاج إلى بعض مشغل تقسيم / مودم، ولكن لحساب مجموعة لا تضطر إليها.
في الأساس، يمكنك فقط استبعاد الأرقام التي تعد مضاعفات أعجبت في وقت سابق، كما هي (بحكم التعريف) وليس الأعداد نفسها.
لن أعطي التنفيذ الكامل، حيث سيكون من السهل، وهذا هو النهج في رمز الزائفة. (على جهازي، يقوم التنفيذ الفعلي بحساب جميع الأعداد الأولية في sytem.int32 (2 بيليون) في غضون 8 ثوان.
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
الحل يتطلب فهم جيد لعمليات bitwise. لكنها طرقها وسبل أسرع. يمكنك أيضا آمنة نتيجة النتيجة على القرص، إذا كنت في حاجة إليها للاستخدام لاحقا. يمكن أن تكون نتيجة 17 * 10 ^ 9 صفقة مع 1 جيجابايت، وتحاسبة مجموعة النتائج هذه تستغرق حوالي دقيقتين كحد أقصى.
أعلم أن هذا سؤال قديم هادئ، ولكن بعد القراءة هنا:غربال eratosthenes wiki
هذه هي الطريقة التي كتبتها من فهم الخوارزمية:
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
في الحلقة الأولى، نملأ مجموعة من المنطمنون مع True.
ستبدأ ثاني حلقة من 2 من 2 لأن 1 ليس عداما وسيحقق ما إذا كان الرقم الأول لا يزال غير متغير ثم قم بتعيين خطأ في فهرس J.
آخر حلقة نحن فقط الطباعة عندما يكون رئيس الوزراء.
مشابه جدا - من تمرين لتنفيذ غربال eratosthenes في C #:
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
رئيس مساعد حساب سريع جدا
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
يمكنك استخدام مفهوم الرقم الرئيسي العادي يجب أن اثنين فقط من العوامل (واحد وحده). لذلك تفعل مثل هذا، طريقة سهلة
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
يعرض هذا الحل جميع الأرقام الأولية بين 0 و 100.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
هذه هي أسرع طريقة لحساب الأرقام الرئيسية في C #.
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
هناك بعض الطرق المثلى جدا لتنفيذ الخوارزمية. ولكن إذا كنت لا تعرف الكثير عن الرياضيات، فأنت ببساطة اتبع تعريف Prime كشرط: رقم غير قابل للقسط فقط بنسبة 1 وبين نفسه (ولا شيء آخر)، إليك بسيطة لفهم رمز للأرقام الإيجابية.
public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
نظرا لأن كل عدد قابل للقسمة بنسبة 1 وبين نفسه، نبدأ في التحقق من 2 فصاعدا حتى الرقم مباشرة قبل نفسه. هذا هو السبب الأساسي.
يمكنك القيام بذلك أيضا:
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
