ขอบคุณ kenessar ที่ตอบครับ วิธีการของคุณดีครับ
แต่ถ้าในการคำนวณ ถ้าเราตรวจสอบจำนวนที่เป็นจำนวนเฉพาะจะช้ามาก
เนื่องจากว่าต้องทำการหารด้วยจำนวนที่น้อยกว่าทุกตัวครับ

ถ้าจำนวนนั้นมาก ๆ ก็จะทำให้ช้าครับ

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

ยกตัวอย่างเช่น
ผมจะตรวจว่าเลข5กับ6เป็นจำนวนเฉพาะหรือไม่
ผมต้องหารแล้วดูเศษ อันไหนลงตัวเกินสองครั้ง มันไม่ใช่จำนวนเฉพาะแล้วครับ

5 หาร 1 = 5 เศษ 0
5 หาร 2 = 2 เศษ 1
5 หาร 3 = 1 เศษ 2
5 หาร 4 = 1 เศษ 1
5 หาร 5 = 1 เศษ 0

สังเกตนะครับว่าหารลงตัวแค่เลข 1 กับตัวมันเอง
ฉะนั้นฟันธง "5 คือจำนวนเฉพาะ"

6 หาร 1 = 6 เศษ 0
6 หาร 2 = 3 เศษ 0
6 หาร 3 = 2 เศษ 0
6 หาร 4 = 1 เศษ 2
6 หาร 5 = 1 เศษ 1
6 หาร 6 = 1 เศษ 0

เอาล่ะครับ จำนวนเฉพาะต้องหารลงตัวแค่ 1 กับตัวมันเองใช่มั้ยครับ
แต่ไอ้เลข 6 นี่จำนวนอื่นๆหารมันลงตัวได้ แล้วมีจำนวนหารลงตัวได้ถึง 4 ตัว

ฉะนั้น "6 ไม่ใช่จำนวนเฉพาะ"

----------------------------------------------------------
การตรวจจับได้ว่าเลขนั้นเป็นจำนวนเฉพาะหรือเปล่า โจทย์บอกเอาไว้ว่า จำนวนเฉพาะคือจำนวนที่หารตัวมันเองและเลข 1 ลงตัว เลขอื่นจะหารมันลงตัวไม่ได้เลย

เคล็ดลับอยู่ที่ "หารลงตัวได้ไม่เกินสองครั้ง"

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

หลังการตรวจสอบแต่ละจำนวน อย่าลืม เซ็ต 0 ให้ตัวนับด้วยนะครับ

ถ้าอยากให้โปรแกรมคำนวณเร็ว ก็ให้ตรวจสอบตัวนับไปในตัวด้วยครับ ถ้าเกิน 2 ปุ๊บ ใช้คำสั่ง break ออกจากลูปเลย

-------------------------------------------------------------
ตัวอย่างโจทย์ปัญหา (มันเป็นภาษาจาวานะครับ)

จงเขียนโปรแกรมเพื่อคำนวณหาตัวเลขที่เป็นจำนวนเฉพาะ 100 ตัวแรก โดยให้แสดงผลบรรทัดละ 10 ตัว ดังตัวอย่างต่อไปนี้


2 3 5 7 11 13 17 19 23 29

31 37 ...

...

-------------------------------------------------
class Prime
{
public static void main(String[] args)
{
int prime=0,i=1,col=1,count=0;
while (prime<100)
{
for (int j=1 ; j<=i ; j++ )
{
if (i%j==0)
{
count++;
}
} // end of for

if (count<=2)
{
if (col>10)
{
col=1;
System.out.println("");
}
System.out.print(i+"\t");
prime++;
col++;
}
i++;
count=0;
} //end of while
} //end of main()
} //end of class Prime

-------------------------------------------------------

ช่วยดูทีครับ(อันนี้ source ถูกต้อง)
ตรวจสอบว่าเป็นจำนวนเฉพาะ
ตรวจสอบว่าเป็นจำนวนเฉพาะ
บทความอันนี้ผมพยายามเขียนให้ทุกคนเข้าใจแม้ไม่ได้เรียนอัลกอริทึมหรือภาษา C ภาษา Python หรือภาษาอื่น ๆ ก็ตาม

ผมมีปัญหาเรื่องขั้นตอนการหาจำนวนเฉพาะด้วยคอมพิวเตอร์ ไม่แน่ใจว่าวิธีนี้ถูกต้องหรือเปล่าดังนั้นจึงขอให้ผู้ที่มีความรู้หรือพบข้อผิดพลาดในวิธีการนี้ช่วย โพส ตอบด้วยครับ

จากความเข้าใจของผมคือ จำนวนเฉพาะคือจำนวนที่ มีเพียง 1 และตัวมันเองเท่านั้นที่หารลงตัว (คิดแต่จำนวนเฉพาะบวกเท่านั้น) ผมได้วิธีการจากหนังสือคอมฯ ทั่วไปวิธีหนึ่งซึ่งเป็นวิธีที่ถูกต้องแต่จะช้าถ้าจำนวนที่ต้องการตรวจสอบมีค่ามากๆ คือวิธีดังนี้คือ

สมมติว่าผมต้องการเช็คว่า 1009 เป็นจำนวนเฉพาะหรือไม่
วิธีการคือใช้จำนวนตั้งแต่ 2 ถึง 1008 หารแล้วดูว่ามีตัวใดที่หารลงตัวหรือไม่
ถ้ามีตัวใดที่หารแล้วลงตัวก็ไม่ใช่จำนวนเฉพาะ

แล้วผมก็ตั้งตารอ คอมพิวเตอร์ก็คิดเริ่มจาก
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
…………………………., …………………………….., ………………………………..,
886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008
คิดดูครับว่าต้องตรวจสอบด้วยตัวเลขมากมายขนาดไหน
และแล้วจากที่ผมคิดว่า 1009 มันลงท้ายด้วย 9 น่าจะหารด้วย 3 ลงตัว ผมก็ต้องพบกับความผิดหวัง
เพราะว่า 1009 เป็นจำนวนเฉพาะครับ

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

ก่อนอื่นเราต้องการตรวจสอบว่า 1009 เป็นจำนวนเฉพาะหรือเปล่า
(หลักการของอัลกอริทึมต่อไปนี้คือ ตัดตัวที่ไม่จำเป็นต้องคำนวณออกไป และข้ามเลขคู่)
เราจะเริ่มตรวจสอบด้วยการหาร 1009 ด้วย 2, 3, 4, 5, … ไปเรื่อย จนถึง 1008
เรากำลังหาตัวเลขในกลุ่ม 2, 3, 4, ..., 1008 สักตัวที่หาร 1009 ลงตัวเพื่อบอกว่ามันไม่ใช่จำนวนเฉพาะ

เมี่อตัวหารเป็น 2
ขอบเขตการตรวจสอบ 2 ถึง 1008
1009 หาร 2 = 504.5
หารไม่ลงตัว
มาถึงตอนนี้ผมคิดได้ว่า 1009 หาร 504.5 ก็เท่ากับ 2 เพราะฉะนั้น ถ้า 1009 หารด้วยจำนวนที่มากกว่า 504.5 ก็จะได้ผลลัพท์น้อยกว่า 2 ถ้ามีจำนวนที่ มากกว่า 504.5 ที่หาร 1009 ลงตัวละก็ ผลลัพธ์ก็ต้องออกมาเป็น 1 ครับ และตัวนั้นก็คือ 1009 นั่นเอง แสดงว่าตั้งแต่ 504.5 ถึง 1008 ไม่มีตัวใดที่หาร 1009 ลงตัว เราจึงเพียงตรวจสอบจากตัวเลขที่เหลือคือ 3 ถึง 504 (ไม่ถึง 504.5 เพราะไม่ใช่จำนวนเต็ม)

เมี่อตัวหารเป็น 3
ขอบเขตการตรวจสอบ 3ถึง 504

1009 หาร 3 = 336.3333333
หารไม่ลงตัว
เช่นเดียวกับตัวอย่างข้างบน 1009 หาร ด้วยจำนวนที่มากกว่า 336.33 ย่อมได้น้อยกว่า 3 ถ้ามีตัวเลขที่เป็นจำนวนเต็มที่หาร 336.33 ลงตัว ผลหารจะเป็น 2 หรือ 1 ถ้าหารแล้วได้ 2 แสดงว่า 2 ก็หารตัวตั้ง(1009) ลงตัว
ซึ่งตัวเลขนี้ต้องตรวจพบตั้งแต่ขั้นตอนที่แล้ว ๆ (ขั้นตอนที่หารด้วย 2) แต่ถ้าหารได้ 1 ก็คือ 1009 ซึ่งไม่ใช่ตัวเลขในช่วง 2 ถึง 1008
ดังนั้นจำนวนที่เหลือที่ต้องตรวจสอบคือ 4 ถึง 336


เมื่อตัวหารเป็น 4
เราจะไม่เช็คที่ 4 เพราะถ้า 4 หารลงตัว 2 ก็หารลงตัว ซึ่งเราเช็คไปแล้ว

เมื่อตัวหารเป็น 5
ขอบเขตที่ตรวจสอบคือ 5 ถึง 1009 หาร 5 คือ 201.8
หารไม่ลงตัว
ตัวเลขที่มากกว่า 201.8 ก็หาร 1009 ไม่ลงตัวเช่นกัน เราสรุปจากขั้นตอนที่แล้ว เพราะถ้าหารลงตัว ผลหารจะได้ 1, 2, 3, 4 ซึ่งเราเช็คไปแล้ว

เราทำไปเรื่อย ๆ จนกระทั่งตัวหารเป็น 31
แน่นอน 1009 หาร 31 = 32.548 ไม่ลงตัวอยู่แล้ว
ฉะนั้นเราจึงเหลือตัวเลขที่ต้องตรวจสอบเพียง 32 ถึง 32.548 ซึ่ง เหลือเพียง 32 ตัวเดียว
และ 1009 หาร 32 ได้ 31.531 ไม่ลงตัวเช่นกัน
เราจึงตรวจสอบตัวเลข จาก 3 ถึง 1008 ครบทุกตัวแล้ว ปรากฏว่าไม่มีตัวเลขในช่วงนี้ที่หาร 1009 ลงตัว
ดังนั้น เราสรุปว่า 1009 เป็นจำนวนเฉพาะ
จะเห็นได้ว่า เราตรวจสอบแค่ตัวเลขในช่วง 2 ถึง 32 เท่านั้น เราตรวจสอบเพียง 32-2+1 = 31 จำนวนแต่ในอัลกอริทึมของผมจะข้ามเลขคู่ไปยกเว้น 2 จะเหลือการตรวจสอบเพียง 15 จำนวนเท่านั้น

และต่อไปนี้เป็น code ในภาษา C++ ครับ มีภาษา python อันต่อไปด้วย
bool isprime(const unsigned long input){
if(input==1||input==0)
return false;
if(input==2)//Must add this line alway.
return true;
if((input%2)==0)
return false;
unsigned long endrank=input/2;
unsigned long i;
for(i=3;i<=endrank;i+=2){
if((input%i)==0)
return false;
endrank=input/i;
}
return true;
}
คืนค่า true ถ้าเป็นจำนวนเฉพาะ นอกจากนั้นคือค่า false
ต่อไปเป็น code ภาษา Python
# โค้ดภาษา Python
def isprime(chk):
chk=long(chk)
if(chk==0 or chk==1):
return False
if chk==2 :
return True
if (chk%2)==0 :
return False
endrank=chk/2 # endrank คือตัวสุดท้ายที่จะค้นหา
i=3
while i<=endrank :
if (chk%i)==0 : # chk หารด้วย i แล้วลงตัว
return False
endrank=chk/i
i+=2
print i
return True

วานผู้อ่านช่วยตรวจสอบด้วยนะครับ

ปล. แต่ผมพึ่งจำได้ว่าที่เรียนคณิตศาสตร์มามีวิธีคิดอีกอย่างหนึ่ง
ถ้า 1009 เป็นจำนวนเฉพาะ แล้ว จะไม่มี จำนวนเต็มบวกที่มากกว่า 2 แต่น้อยกว่าหรือเท่ากับ รากที่สองของ 1009 หารลงตัว
ซึ่งมันก็จริง เพราะรากที่สองของ 1009 เท่ากับ 31.76476034853718 (คำนวณด้วย IDLE ของ Python)

นี่เป็นอีกเหตุผลหนึ่งว่าอัลกอริทึมที่เขียนด้วยโปรแกรมเมอร์ ที่เก่งและชำนาญคณิตศาสตร์ มีความรวดเร็ว
แต่บางครั้งอัลกอรึทึมนี้น่าจะเป็นการคิดสร้างสรรค์ที่ดีก็ได้นะครับ ฝึกให้เราคิดหาวิธีที่ดีที่สุด

ขอบคุณ คนที่อ่าน และ Post แสดงความคิดเห็น ที่สำคัญคนที่ช่วยตรวจสอบด้วยนะครับ

noonenodead
(no one no dead)

ช่วยดูทีครับ
ตรวจสอบว่าเป็นจำนวนเฉพาะ
บทความอันนี้ผมพยายามเขียนให้ทุกคนเข้าใจแม้ไม่ได้เรียนอัลกอริทึมหรือภาษา C ภาษา Python หรือภาษาอื่น ๆ ก็ตาม

ผมมีปัญหาเรื่องขั้นตอนการหาจำนวนเฉพาะด้วยคอมพิวเตอร์ ไม่แน่ใจว่าวิธีนี้ถูกต้องหรือเปล่าดังนั้นจึงขอให้ผู้ที่มีความรู้หรือพบข้อผิดพลาดในวิธีการนี้ช่วย โพส ตอบด้วยครับ

จากความเข้าใจของผมคือ จำนวนเฉพาะคือจำนวนที่ มีเพียง 1 และตัวมันเองเท่านั้นที่หารลงตัว (คิดแต่จำนวนเฉพาะบวกเท่านั้น) ผมได้วิธีการจากหนังสือคอมฯ ทั่วไปวิธีหนึ่งซึ่งเป็นวิธีที่ถูกต้องแต่จะช้าถ้าจำนวนที่ต้องการตรวจสอบมีค่ามากๆ คือวิธีดังนี้คือ

สมมติว่าผมต้องการเช็คว่า 1009 เป็นจำนวนเฉพาะหรือไม่
วิธีการคือใช้จำนวนตั้งแต่ 2 ถึง 1008 หารแล้วดูว่ามีตัวใดที่หารลงตัวหรือไม่
ถ้ามีตัวใดที่หารแล้วลงตัวก็ไม่ใช่จำนวนเฉพาะ

แล้วผมก็ตั้งตารอ คอมพิวเตอร์ก็คิดเริ่มจาก
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
…………………………., …………………………….., ………………………………..,
886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008
คิดดูครับว่าต้องตรวจสอบด้วยตัวเลขมากมายขนาดไหน
และแล้วจากที่ผมคิดว่า 1009 มันลงท้ายด้วย 9 น่าจะหารด้วย 3 ลงตัว ผมก็ต้องพบกับความผิดหวัง
เพราะว่า 1009 เป็นจำนวนเฉพาะครับ

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

ก่อนอื่นเราต้องการตรวจสอบว่า 1009 เป็นจำนวนเฉพาะหรือเปล่า
(หลักการของอัลกอริทึมต่อไปนี้คือ ตัดตัวที่ไม่จำเป็นต้องคำนวณออกไป และข้ามเลขคู่)
เราจะเริ่มตรวจสอบด้วยการหาร 1009 ด้วย 2, 3, 4, 5, … ไปเรื่อย จนถึง 1008
เรากำลังหาตัวเลขในกลุ่ม 2, 3, 4, ..., 1008 สักตัวที่หาร 1009 ลงตัวเพื่อบอกว่ามันไม่ใช่จำนวนเฉพาะ

เมี่อตัวหารเป็น 2
ขอบเขตการตรวจสอบ 2 ถึง 1008
1009 หาร 2 = 504.5
หารไม่ลงตัว
มาถึงตอนนี้ผมคิดได้ว่า 1009 หาร 504.5 ก็เท่ากับ 2 เพราะฉะนั้น ถ้า 1009 หารด้วยจำนวนที่มากกว่า 504.5 ก็จะได้ผลลัพท์น้อยกว่า 2 ถ้ามีจำนวนที่ มากกว่า 504.5 ที่หาร 1009 ลงตัวละก็ ผลลัพธ์ก็ต้องออกมาเป็น 1 ครับ และตัวนั้นก็คือ 1009 นั่นเอง แสดงว่าตั้งแต่ 504.5 ถึง 1008 ไม่มีตัวใดที่หาร 1009 ลงตัว เราจึงเพียงตรวจสอบจากตัวเลขที่เหลือคือ 3 ถึง 504 (ไม่ถึง 504.5 เพราะไม่ใช่จำนวนเต็ม)

เมี่อตัวหารเป็น 3
ขอบเขตการตรวจสอบ 3ถึง 504

1009 หาร 3 = 336.3333333
หารไม่ลงตัว
เช่นเดียวกับตัวอย่างข้างบน 1009 หาร ด้วยจำนวนที่มากกว่า 336.33 ย่อมได้น้อยกว่า 3 ถ้ามีตัวเลขที่เป็นจำนวนเต็มที่หาร 336.33 ลงตัว ผลหารจะเป็น 2 หรือ 1 ถ้าหารแล้วได้ 2 แสดงว่า 2 ก็หารตัวตั้ง(1009) ลงตัว
ซึ่งตัวเลขนี้ต้องตรวจพบตั้งแต่ขั้นตอนที่แล้ว ๆ (ขั้นตอนที่หารด้วย 2) แต่ถ้าหารได้ 1 ก็คือ 1009 ซึ่งไม่ใช่ตัวเลขในช่วง 2 ถึง 1008
ดังนั้นจำนวนที่เหลือที่ต้องตรวจสอบคือ 4 ถึง 336


เมื่อตัวหารเป็น 4
เราจะไม่เช็คที่ 4 เพราะถ้า 4 หารลงตัว 2 ก็หารลงตัว ซึ่งเราเช็คไปแล้ว

เมื่อตัวหารเป็น 5
ขอบเขตที่ตรวจสอบคือ 5 ถึง 1009 หาร 5 คือ 201.8
หารไม่ลงตัว
ตัวเลขที่มากกว่า 201.8 ก็หาร 1009 ไม่ลงตัวเช่นกัน เราสรุปจากขั้นตอนที่แล้ว เพราะถ้าหารลงตัว ผลหารจะได้ 1, 2, 3, 4 ซึ่งเราเช็คไปแล้ว

เราทำไปเรื่อย ๆ จนกระทั่งตัวหารเป็น 31
แน่นอน 1009 หาร 31 = 32.548 ไม่ลงตัวอยู่แล้ว
ฉะนั้นเราจึงเหลือตัวเลขที่ต้องตรวจสอบเพียง 32 ถึง 32.548 ซึ่ง เหลือเพียง 32 ตัวเดียว
และ 1009 หาร 32 ได้ 31.531 ไม่ลงตัวเช่นกัน
เราจึงตรวจสอบตัวเลข จาก 3 ถึง 1008 ครบทุกตัวแล้ว ปรากฏว่าไม่มีตัวเลขในช่วงนี้ที่หาร 1009 ลงตัว
ดังนั้น เราสรุปว่า 1009 เป็นจำนวนเฉพาะ
จะเห็นได้ว่า เราตรวจสอบแค่ตัวเลขในช่วง 2 ถึง 32 เท่านั้น เราตรวจสอบเพียง 32-2+1 = 31 จำนวนแต่ในอัลกอริทึมของผมจะข้ามเลขคู่ไปยกเว้น 2 จะเหลือการตรวจสอบเพียง 15 จำนวนเท่านั้น

และต่อไปนี้เป็น code ในภาษา C++ ครับ มีภาษา python อันต่อไปด้วย
bool isprime(const unsigned long input){
if(input==1||input==0)
return false;
if(input==2)//Must add this line alway.
return true;
if((input%2)==0)
return false;
unsigned long endrank=input/2;
unsigned long i;
for(i=3;i<=endrank;i+=2){
if((input%i)==0)
return false;
endrank=input/i;
}
return true;
}
คืนค่า true ถ้าเป็นจำนวนเฉพาะ นอกจากนั้นคือค่า false
ต่อไปเป็น code ภาษา Python
# โค้ดภาษา Python
def isprime(chk):
chk=long(chk)
if(chk==0 or chk==1):
return False
if chk==2 :
return True
if (chk%2)==0 :
return False
endrank=chk/2 # endrank คือตัวสุดท้ายที่จะค้นหา
i=3
while i<=endrank :
if (chk%i)==0 : # chk หารด้วย i แล้วลงตัว
return False
endrank=chk/i
i+=2
print i
return True

วานผู้อ่านช่วยตรวจสอบด้วยนะครับ

ปล. แต่ผมพึ่งจำได้ว่าที่เรียนคณิตศาสตร์มามีวิธีคิดอีกอย่างหนึ่ง
ถ้า 1009 เป็นจำนวนเฉพาะ แล้ว จะไม่มี จำนวนเต็มบวกที่มากกว่า 2 แต่น้อยกว่าหรือเท่ากับ รากที่สองของ 1009 หารลงตัว
ซึ่งมันก็จริง เพราะรากที่สองของ 1009 เท่ากับ 31.76476034853718 (คำนวณด้วย IDLE ของ Python)

นี่เป็นอีกเหตุผลหนึ่งว่าอัลกอริทึมที่เขียนด้วยโปรแกรมเมอร์ ที่เก่งและชำนาญคณิตศาสตร์ มีความรวดเร็ว
แต่บางครั้งอัลกอรึทึมนี้น่าจะเป็นการคิดสร้างสรรค์ที่ดีก็ได้นะครับ ฝึกให้เราคิดหาวิธีที่ดีที่สุด

ขอบคุณ คนที่อ่าน และ Post แสดงความคิดเห็น ที่สำคัญคนที่ช่วยตรวจสอบด้วยนะครับ

noonenodead
(no one no dead)

ผมมีข้อสงสัยช่วยอบทีครับ
ทดสอบว่าเป็นจำนวนเฉพาะ.pdf

เป็นบทความที่ดีมากครับ แต่หลายๆปัญหาก็ค้างคาใจผมเหมือนกัน แก้ไม่ค่อยออกเลยบางที หุหุ

ชอบครับ

Star to You

ปัญหาพวกนี้ถึงจะเป็นคำถามที่คลาสสิก แต่ก็ทำให้งงได้ในบางทีเหมือนกันนะครับ

อุอุ เรื่องนี้อนกันยาก นะ อัลกอเนี่ย ขึ้นอยู่กับ ความฉลาด(IQ)ของแต่ละคนด้วย ยิ่ง โปรแกรมเมอร์ ถ้าอยากเก่ง ต้องเขียนโปรแกรมให้ อัลกอ ดีถ้าไม่ดี ไม่ดังแน่ คริๆ เขียนโปรแกรมง่ายนะ ถ้าจะให้มันคิดคำตอบออก แต่ยากตรงที่ทำยังไง ให้มันสั้นสุด ดีสุด