คราวที่แล้ว เราพูดถึงลำดับ 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 10001^st 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 : 4738 Pageviews.
Tweet