Just algorithm!
มาสร้างลำดับจำนวนเฉพาะด้วย C# กัน

คราวที่แล้ว เราพูดถึงลำดับ Fibonacci ซึ่งถือว่าเป็นลำดับที่ง่ายมาก
เลข Fibonacci ตัวถัดไป มาจากตัวเลขตัวก่อนหน้า 2 ตัวเท่านั้น
คราวนี้ เรามาพูดถึงลำดับ จำนวนเฉพาะ กัน
ซึ่งจำนวนเฉพาะนี้ความท้าทายของมันคือ ยิ่งคำนวนจะยิ่งยากขึ้นเรื่อย ๆ
เพราะเลขจำนวนเฉพาะตัวถัดไป ต้องใช้ตัวเลขก่อนหน้าทุกตัวมาคำนวน
การคำนวนจำนวนเฉพาะนี้ท้าทายมาก
โดยถึงกับมี โครงการ สำหรับขอพลัง Computer ร่วมกันประมวลผลจำนวนเฉพาะกัน
และมีการ ตั้งรางวัล สำหรับผู้ค้นพบจำนวนเฉพาะลำดับที่มากที่สุดได้ Smiley

จำนวนเฉพาะคือจำนวนนับที่มีตัวหารแค่ 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.

จำนวนเฉพาะเป็น ตัวประกอบ เฉพาะของจำนวนเต็มทุกตัว
มีประโยชน์ในการวิเคราะห์โจทย์พีชคณิต
นอกจากนี้ จำนวนเฉพาะยังถูกนำไปใช้สำหรับการ เข้ารหัส เพื่อรักษาความปลอดภัย Smiley

Technic ที่ผมใช้สำหรับการสร้างลำดับจำนวนเฉพาะคือ Sieve of Eratosthenes
ซึ่งเป็นการเอาจำนวนเฉพาะ มาตัดเลขที่เป็นผลคูณของจำนวนเฉพาะนั้นออกไป
เช่น เลข 3 ก็เอาไปตัดเลข 6, 9, 12, 15, ...
เมื่อทดสอบกับเลขจำนวนก่อนหน้าทุกตัวแล้ว เลขที่ไม่ถูกตัดก็คือจำนวนเฉพาะนั่นเอง
ผมได้พัฒนาให้ Algorithm ของตัวเก็บจำนวนเฉพาะ เก็บเฉพาะเลขคี่
และปรับ Memory ให้เติบโตตามลำดับของจำนวนเฉพาะ Smiley

และนี่เป็น 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 ล้านหลักเองครับ Smiley

เรื่องของลำดับยังไม่จบนะครับ ตอนหน้ามารู้จักกับลำดับ 3 เหลี่ยมมุมฉากกัน ???
เป็นยังไงติดตามชมด้วยนะครับ

* อ่านจบแล้ว กรุณา Comment ด้วยครับ เพื่อเป็น Feedback และเป็นกำลังใจ
* บทความนี้คัดลอกได้ แต่ต้องมี Link หรือ Url กลับมาที่หน้านี้ และเมื่อคัดลอกแล้วกรุณา Comment แจ้งด้วยครับ




Create Date : 18 กรกฎาคม 2551
Last Update : 9 สิงหาคม 2551 15:35:55 น. 14 comments
Counter : 4468 Pageviews.

 
เคยเรียนมาตอนปีหนึ่ง

แทบเอาชีวิตไม่รอดเลย


โดย: บุปผาชน (นภานุภาพ ) วันที่: 18 กรกฎาคม 2551 เวลา:18:43:43 น.  

 
ยาววววววว - -

ขอเวลานั่งอ่านดูซักพัก

ขอบคุณเจ้าของบลอคมากๆคร้าบ


โดย: Autopilot IP: 158.108.237.174 วันที่: 18 กรกฎาคม 2551 เวลา:21:34:45 น.  

 
โอ๊ว ยาว...เทพ..พเจ้า

ขอบคุณนะครับ ได้เข้ามาอ่านที่ไรได้ความรู้เพิ่มทุกที่


โดย: PureSnow IP: 124.120.197.58 วันที่: 18 กรกฎาคม 2551 เวลา:23:07:52 น.  

 
//case.eng.ku.ac.th/aerowebboard/index.php?showtopic=9084

หาจำนวนเฉพาะแบบสั้น


โดย: airai IP: 158.108.234.161 วันที่: 25 กรกฎาคม 2551 เวลา:22:22:47 น.  

 
Method ในการหาจำนวนเฉพาะแบบใช้ Mod กับแบบ Sieve มีข้อดีข้อเสียต่างกันครับ

แบบ Mod คือทดลองหารทีละตัว วิธีนี้เขียนง่าย ไม่เปลือง memory แต่เมื่อหาจำนวนเฉพาะตัวเลขมาก ๆ จะค่อนข้างช้า

แบบ Sieve คือการเก็บตัวเลขที่คำนวนแล้วไว้ใน BitArray จะดูยุ่งยากกว่า แต่ทำงานได้เร็วกว่ากันมากครับ


โดย: chaowman วันที่: 25 กรกฎาคม 2551 เวลา:23:14:21 น.  

 
How I can write a program to multiply two 2*2 matrices and display the result.
Sample Output

Enter A[1,1]: 1
Enter A[1,2]: 2
Enter A[2,1]: 3
Enter A[2,2]: 4
Enter A[1,1]: 5
Enter A[1,2]: 6
Enter A[2,1]: 7
Enter A[2,2]: 8
Matrix A*B is:
19 22
43 50



This is the exercise Lab in my class and please help me !!


โดย: airai IP: 202.176.104.124 วันที่: 9 กันยายน 2551 เวลา:11:42:07 น.  

 
ไม่รู้ยังต้องการคำตอบอยู่รึเปล่านะครับ
แต่เดี๋ยวคืนนี้จะทำเรื่อง Matrix แล้วจะ Post ขึ้นให้
เผอิญไม่ได้เช็ค Blog เลยครับ


โดย: chaowman วันที่: 19 พฤศจิกายน 2551 เวลา:10:06:47 น.  

 
ขอบคุณมาก ๆๆๆๆๆ เลยค่ะ

หนูกำลัง หา ไปทำการบ้านพอดีเลย

หายากมากเรยที่จะเข้าใจง่ายแบบนี้

ไม่หวงวิชาด้วย

ขอบคุณมากๆเลยค่ะจากใจเลย

* ขออนุญาตแวะมาอีกบ่อย ๆ นะคะ T-T


โดย: ปูเป้ IP: 118.172.208.225 วันที่: 7 กรกฎาคม 2552 เวลา:22:34:15 น.  

 
เก่งจังเลยนะจะตัวเอง


โดย: furn IP: 192.168.22.39, 118.173.49.197 วันที่: 28 มกราคม 2553 เวลา:11:20:44 น.  

 
ตอนปี หนึ่งได้เรียนแบบนี้ก็ดีซิ นี่จบแล้วยังทำไม่ค่อยเป็นเลย
- -* ไม่อยากว่า ราชภัฏ เลยเสียเงินเข้าเรียนเอกชนคงเข้มกว่านี้


โดย: คนน้อยใจ IP: 112.142.163.185 วันที่: 9 พฤษภาคม 2553 เวลา:13:05:27 น.  

 
มีแต่คนเรียนกันตอนปี1อ่ะ ทำไมอาจารที่ร.ร.ให้มาทำตอนม.6เนี่ย TT ตั้ง10ข้อTT


โดย: namm IP: 125.27.135.59 วันที่: 6 สิงหาคม 2553 เวลา:19:57:49 น.  

 
อ่านดูแล้วก็งงๆเพราะว่ายังไม่เคยเรียน


โดย: 27630 IP: 110.77.232.198 วันที่: 8 มีนาคม 2554 เวลา:14:38:12 น.  

 
กราบเรียนผู้ใจบุญช่วยเขียนโปรแกรม
c#2008 ให้หน่อยครับจะขอบพระคุณเป็นอย่างสูง
คือผมลองเขียนแล้วมันก็ไม่ได้ซักทีได้แต่ก็ไม่ตรงช่วยหน่อยนะครับ
‎1.รับข้อมูลจำนวนเต็มจากผุ้ใช้​ จะหยุดรับข้อมูลเมื่อผลรวมของข้​อมูลนั้น มีค่ามากกว่า 200 ให้หาว่ามี่การรับข้อมูล ทั้งหมดกี่จำนวน
2.เขียนโปรแกรมเพื่อรับข้อมูลตั​วอักษารจากผู้ใช้ หากผู้ใช้ป้อนตัวอักษร a,b.x ให้ขึ้นข้อมความว่า "Hanaga"ป้อนตัวอักษร u,d,p ให้ขึ้นข้อความว่า "Bingo" ป้อนตัวอักษร g ให้ขึ้นข้อความว่า "Google" ป้อนตัวอักษรอื่น ๆ ให้ขึ้นข้อความว่า "Yappadappadoooo"
3.เขียนโปรแกรมเพื่อบวกเลขจำนวน​เต็มคี่ N จำนวนโดยรับค่า N จากผู้ใช้


โดย: แม็ก IP: 223.205.168.223 วันที่: 5 สิงหาคม 2554 เวลา:15:50:46 น.  

 
ขอบคุณมากๆนะค่ะ


โดย: นุชชรี IP: 202.29.22.247 วันที่: 10 กันยายน 2554 เวลา:11:16:45 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 
รหัสส่งข้อความ
กรุณายืนยันรหัสส่งข้อความ

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.