จำนวนเฉพาะ

\"จํานวนเฉพาะ\" หรือ ไพรม์ นัมเบอร์ (Prime number) คือ จาํ นวน ธรรมชาติที่มีตวั หารท่ีเป็นบวกอยู่ 2 ตวั คือ 1 กบั ตวั มนั เอง เช่น 2, 3, 5, 7, 11, 13 และ 17 เป็นตน้ และสาํ หรับเลข 1 น้นั ใหต้ ดั ทิง้ เพราะ 1 ไม่เป็นจาํ นวนเฉพาะ จํานวนเฉพาะ 1-100 มที ้งั หมด 25 ตวั ดังนี้ 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 จาํ นวนเฉพาะ 1-200 มที ้งั หมด 46 ตัว ดังนี้ 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197 และ 199

จาํ นวนเฉพาะ 1-1000 มีท้งั หมด 176 ตวั ดังนี้ 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 221, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 403, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 499, 503, 509, 521, 523, 533, 541, 547, 559, 563, 569, 571, 577, 587, 593, 599, 601, 607, 611, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 689, 691, 701, 709, 719, 727, 733, 739, 743, 751, 767, 769, 773, 787, 793, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 871, 877, 881, 883, 887, 907, 911, 919, 923, 929, 937, 941, 947, 949, 953, 967, 971, 977, 983, 991 และ 997

สําหรับวธิ ตี รวจสอบความเป็ นจํานวนเฉพาะ สามารถทาํ ได้ ดงั นี้ สมมติเขาถามวา่ 331 เป็นจาํ นวนเฉพาะรึเปล่า ทุกคนกค็ งจะเริ่มดว้ ยการ ประมาณค่ารากที่สองของ 331 ซ่ึงไดป้ ระมาณเกือบ ๆ 18 จากน้นั กเ็ ริ่มเอาจาํ นวน เฉพาะไปหาร 331 ดู โดยเริ่มจาก 2 3 5 7 ไปเร่ือย ๆ แต่พอเราลองไปจนถึง 17 แลว้ ยงั ไม่มีจาํ นวนเฉพาะสกั ตวั หาร 331 ลงตวั เรากห็ ยดุ และสรุปวา่ 331 เป็นจาํ นวน เฉพาะ โดยไม่ตอ้ งลองเอาจาํ นวนเฉพาะอ่ืนๆ ไปหาร 331 อีกต่อไป มีวธิ ีคิดดงั น้ีคือ ให้ n เป็นจาํ นวนนบั ใด ๆ (n เป็นจาํ นวนเฉพาะหรือไม่กเ็ ป็นจาํ นวนประกอบเพยี ง อยา่ งใดอยา่ งหน่ึง) - สมมติวา่ n เป็นจาํ นวนประกอบ - จาํ นวนประกอบคือจาํ นวนที่มีจาํ นวนอื่นนอกจาก 1 และตวั มนั เอง ที่หารมนั ลงตวั - ดงั น้นั มีจาํ นวนนบั a โดย a หาร n ลงตวั และ 1 < a < n - นน่ั คือจะมีจาํ นวนนบั b ท่ี 1 < b < n และ n = a * b - โดยไม่เสียนยั สาํ คญั กาํ หนดให้ a <= b (ถา้ a > b กใ็ หส้ ลบั ค่า a กบั b) - สังเกตวา่ a = รากที่สองของ (a^2) <= รากที่สองของ (a*b) = รากท่ีสอง ของ n