มาสร้างลำดับจำนวนเฉพาะด้วย C# กัน
คราวที่แล้ว เราพูดถึงลำดับ Fibonacci ซึ่งถือว่าเป็นลำดับที่ง่ายมาก เลข Fibonacci ตัวถัดไป มาจากตัวเลขตัวก่อนหน้า 2 ตัวเท่านั้น คราวนี้ เรามาพูดถึงลำดับ จำนวนเฉพาะ กัน ซึ่งจำนวนเฉพาะนี้ความท้าทายของมันคือ ยิ่งคำนวนจะยิ่งยากขึ้นเรื่อย ๆ เพราะเลขจำนวนเฉพาะตัวถัดไป ต้องใช้ตัวเลขก่อนหน้าทุกตัวมาคำนวน การคำนวนจำนวนเฉพาะนี้ท้าทายมาก โดยถึงกับมี โครงการ สำหรับขอพลัง Computer ร่วมกันประมวลผลจำนวนเฉพาะกัน และมีการ ตั้งรางวัล สำหรับผู้ค้นพบจำนวนเฉพาะลำดับที่มากที่สุดได้ 
จำนวนเฉพาะคือจำนวนนับที่มีตัวหารแค่ 2 ตัว นั่นก็คือเลข 1 และตัวมันเอง ลำดับจำนวนเฉพาะที่น้อยกว่า 100 คือ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
จำนวนเฉพาะเป็น ตัวประกอบ เฉพาะของจำนวนเต็มทุกตัว มีประโยชน์ในการวิเคราะห์โจทย์พีชคณิต นอกจากนี้ จำนวนเฉพาะยังถูกนำไปใช้สำหรับการ เข้ารหัส เพื่อรักษาความปลอดภัย 
Technic ที่ผมใช้สำหรับการสร้างลำดับจำนวนเฉพาะคือ Sieve of Eratosthenes ซึ่งเป็นการเอาจำนวนเฉพาะ มาตัดเลขที่เป็นผลคูณของจำนวนเฉพาะนั้นออกไป เช่น เลข 3 ก็เอาไปตัดเลข 6, 9, 12, 15, ... เมื่อทดสอบกับเลขจำนวนก่อนหน้าทุกตัวแล้ว เลขที่ไม่ถูกตัดก็คือจำนวนเฉพาะนั่นเอง ผมได้พัฒนาให้ Algorithm ของตัวเก็บจำนวนเฉพาะ เก็บเฉพาะเลขคี่ และปรับ Memory ให้เติบโตตามลำดับของจำนวนเฉพาะ 
และนี่เป็น Type สำหรับเก็บจำนวนเฉพาะ
public class PrimeStore { const int defaultCapacity = 1024; BitArray _store; int _lastIndex;
public PrimeStore() { _store = new BitArray(defaultCapacity, true); } public PrimeStore(int capacity) { _store = new BitArray(capacity, true); }
public bool IsPrime(int num) { if (num < 2) return false; if (num == 2) return true; if ((num & 1) == 0) return false;
int index = (num - 3) >> 1; testPrime(index); return _store.Get(index); } void testPrime(int index) { if (index <= _lastIndex) return;
ensureCapacity(index);
for (int prime; _lastIndex < index; _lastIndex++) { if (_store.Get(_lastIndex)) { prime = (_lastIndex << 1) + 3; applyPrime(prime, _lastIndex); } } } void ensureCapacity(int index) { int lastIndex = _store.Count - 1; if (index <= lastIndex) return;
int newCapacity = _store.Count; while (index >= newCapacity) newCapacity = newCapacity * 2;
int newSize = newCapacity / 32; int[] array = new int[newSize]; _store.CopyTo(array, 0); for (int i = _store.Count / 32; i < newSize; i++) array[i] = -1; _store = new BitArray(array);
for (int i = 0, prime, num; i < _lastIndex; i++) { if (_store.Get(i)) { prime = (i << 1) + 3; num = lastIndex - i; applyPrime(prime, num - (num % prime) + i); } } } void applyPrime(int prime, int index) { index += prime; int capacity = _store.Count; for (; index < capacity && index > 0; index += prime) _store.Set(index, false); } }
PrimeStore นี้มีแค่ method เดียวคือ IsPrime สำหรับตอบว่าเลขที่ส่งมาเป็นจำนวนเฉพาะหรือไม่ เช่น ต้องการรู้ว่า 34567 เป็นจำนวนเฉพาะหรือไม่ เขียนได้ดังนี้
bool isPrime = new PrimeStore().IsPrime(34567);
แต่งานของเรายังไม่จบเพียงเท่านี้ เราต้องสามารถแสดงลำดับจำนวนเฉพาะได้ด้วย และ Type นี้แทนลำดับจำนวนเฉพาะ (BaseSequence มาจาก Post นี้)
public class Prime : BaseSequence<long> { PrimeStore _primeStore; const long maxStoredValue = 2147483647L;
public Prime() { _primeStore = new PrimeStore(); } public Prime(int capacity) { _primeStore = new PrimeStore(capacity); }
protected override IEnumerable<long> Enumerate() { yield return 2L;
long value = 3L; yield return value;
while (true) { do value += 2L; while (!Contains(value)); yield return value; } } public bool Contains(long value) { if (value < maxStoredValue) return _primeStore.IsPrime((int)value);
return Factors(value).First() == value; } public IEnumerable<long> Factors(long value) { if (value < 2L) yield break;
using (IEnumerator<long> enumerator = Enumerate().GetEnumerator()) { enumerator.MoveNext();
long factor = enumerator.Current; long pow = factor * factor; long num = value; long mod, num2;
while (num >= pow) { num2 = Math.DivRem(num, factor, out mod); if (mod == 0L) { num = num2; yield return factor; } else { enumerator.MoveNext(); factor = enumerator.Current; pow = factor * factor; } } yield return num; } } }
Type นี้นอกจากจะสร้างลำดับจำนวนเฉพาะได้แล้ว ยังมีอีก 2 methods คือ Contains กับ Factors Contains ก็คือ IsPrime นั่นเอง มีไว้สำหรับทดสอบว่าเลขใดเลขหนึ่ง เป็นจำนวนเฉพาะหรือไม่ Factors เป็น method สำหรับแยกตัวประกอบเฉพาะออกมาทีละตัว
มาต่อกันสำหรับวิธีใช้ลำดับจำนวนเฉพาะและโจทย์จาก projecteuler.net. Find the largest prime factor of 317584931803. "หาตัวประกอบเฉพาะที่มากที่สุดของเลข 317584931803"
Console.WriteLine(new Prime().Factors(317584931803).Max()); //3919
Find the 10001st prime. "หาเลขจำนวนเฉพาะลำดับที่ 10001"
Console.WriteLine(new Prime().ElementAt(10000)); //104743
เห็นไหมครับว่าลำดับจำนวนเฉพาะนั้นใช้ง่ายนิดเดียว คุณไม่ลองเอา Code ด้านบนไปพัฒนาต่อ เพื่อหาจำนวนเฉพาะเลขที่มากที่สุดแล้วไปรับรางวัลหรือครับ เป้าหมายต่อไป เค้าต้องการแค่เลขจำนวนเฉพาะความยาว 10 ล้านหลักเองครับ 
เรื่องของลำดับยังไม่จบนะครับ ตอนหน้ามารู้จักกับลำดับ 3 เหลี่ยมมุมฉากกัน ??? เป็นยังไงติดตามชมด้วยนะครับ
* อ่านจบแล้ว กรุณา Comment ด้วยครับ เพื่อเป็น Feedback และเป็นกำลังใจ * บทความนี้คัดลอกได้ แต่ต้องมี Link หรือ Url กลับมาที่หน้านี้ และเมื่อคัดลอกแล้วกรุณา Comment แจ้งด้วยครับ
Create Date : 18 กรกฎาคม 2551 |
Last Update : 9 สิงหาคม 2551 15:35:55 น. |
|
14 comments
|
Counter : 8246 Pageviews. |
 |
|
แทบเอาชีวิตไม่รอดเลย