สวัสดีและยินดีต้อนรับ.
ฉันต้องการที่จะให้ สาธิตวิธีแก้ปัญหาสำหรับความท้าทายครั้งก่อนของเราซึ่ง
คือการเขียนโปรแกรมสร้างจำนวนเฉพาะ
และอีกครั้ง ประเด็นทั้งหมด ของโปรแกรมนี้คือการใช้อาร์เรย์ คุณต้องการเรียนรู้ทั้งหมด
เกี่ยวกับอาร์เรย์และทำสิ่งนี้
ฉันก็เลยพยายามอธิบาย อัลกอริธึมเลขเฉพาะก่อน
แต่ขอพูดอีกครั้งว่า คุณสามารถตรวจสอบได้ว่าจำนวนเฉพาะเป็นจำนวนเฉพาะหรือไม่
จำนวนเฉพาะ หมายความว่า เอ่อ หารด้วยจำนวนเฉพาะตัวอื่นไม่ลงตัว
นั่นคืออัลกอริทึมของความคิด ที่เราจะผ่านไป
และด้วยเหตุนั้นก็คือ จำนวนเฉพาะเป็นเพราะสามารถแสดงจำนวนเต็มใดๆ ที่ไม่ใช่จำนวนเฉพาะได้
เป็นปัจจัยสำคัญหลายประการ
ตัวอย่างเช่น 20 มี ตัวประกอบเฉพาะ 2 2 และ 5
เมื่อรู้อย่างนี้แล้ว มันก็จะบอกคุณเอง ว่าจำนวนเฉพาะนั้นหารด้วยจำนวนเฉพาะใด ๆ
หารด้วยจำนวนเฉพาะไม่ลงตัว
จึงสามารถช่วยให้ การทดสอบจำนวนเฉพาะที่มีประสิทธิภาพ
สิ่งที่คุณทำได้ก็คือคุณ สามารถตรวจสอบจำนวนเฉพาะที่สร้างไว้ก่อนหน้านี้
เพื่อให้เราสามารถจัดเก็บก่อนหน้านี้ของเราได้
สร้างจำนวนเฉพาะในอาร์เรย์ และนั่นคือวิธีที่เรา สามารถหาข้อมูลนี้ได้
นอกจากนี้ จำนวนเต็ม 9 ไพรม์ใดๆ n ต้อง มีปัจจัยหนึ่งเป็นจำนวนเต็มที่น้อยกว่าหรือ
เท่ากับสแควร์รูทของ n
แปลว่ามันจำเป็นเท่านั้น เพื่อตรวจสอบว่าจำนวนเต็มที่กำหนดให้เป็นจำนวนเฉพาะหรือไม่โดยการทดสอบหาคู่
การหารตัวประกอบเฉพาะทั้งหมดจนถึงรากที่สองของจำนวนเต็ม
ดังนั้นคุณสามารถหยุดตรงนั้นและ อีกครั้งมันทำให้มีประสิทธิภาพมากขึ้น
นี้จะเห็นได้ชัดเจน ในวงในของฉันเมื่อฉันกระโดดออกไปเพื่อตรวจสอบว่าฉัน
ไม่พบจำนวนเฉพาะ
ฉันจะกระโดดออกไปถ้าฉันไปถึง รากที่สองของจำนวนเต็ม มันคือเงื่อนไขทางออก
ให้ผ่านและทางไป ที่ตรวจสอบได้คือคุณบอกว่า
p หารด้วยจำนวนเฉพาะ มากกว่าไพรม์ sub-I และเราจะใช้มันในวงในสุดถึง ทดสอบว่าค่าของ
p เกินรากที่สองของ I ของไพรม์หรือไม่
มาเลยเอาโค้ดมาเลย บล็อกเพื่อเริ่มเขียนโค้ด
เรากำลังจะทำพื้นฐาน ที่นี่ สร้างโครงการ
เราจะตั้งชื่อโปรเจ็กต์ของเราว่าไพรม์
ไปที่โครงการใหม่แล้วไปที่คอนโซลแอปพลิเคชัน
และเราจะตั้งชื่อมันว่าไพรม์
พูดต่อไปเราจะไม่ไป เพื่อใช้คอมไพเลอร์นี้
ฉันกำลังเล่นอยู่รอบๆ คอมไพเลอร์ ฉันต้องการให้แน่ใจว่าฉันมีคอมไพเลอร์ที่ถูกต้อง
ฉันจะ เพียงใช้คอมไพเลอร์ cygwin
ดังนั้นจึงสร้าง main ของฉัน ไฟล์ต้นฉบับและว่างเปล่า
มากำจัด printf . กันเถอะ และเริ่มเขียนโค้ด
เราจะรวม a ไฟล์ที่เรียกว่าวัวมาตรฐาน
ฉันยังไม่ได้ทำสิ่งนี้ ฉันเคย การสร้างบูลีนของฉันเป็นขีดล่าง
มาทดสอบกันหน่อย ฉันต้องการที่จะสามารถทำบูล
ตอนนี้เราก็ใช้บูลได้แล้ว
โดยปกติใน C89 ประเภทข้อมูล สำหรับจริงหรือเท็จคือขีดเส้นใต้บูล
แต่จริงๆแล้วคุณสามารถมีประเภท คำจำกัดความในเวอร์ชันที่ใหม่กว่าและในไฟล์บูลมาตรฐานถึง
เพียงใช้บูลส์และยังให้คุณใช้ค่าเท็จจริงเป็นค่าได้อีกด้วย
เราเลยต้องสร้างมันขึ้นมา ตัวแปรที่นี่ก่อน
เรากำลังจะสร้างเคาน์เตอร์ของเรา ซึ่งเราจะตั้งชื่อว่า p
นั่นจะเป็นเคาน์เตอร์ของเรา สำหรับลูปของเราตั้งแต่เมื่อเราตรวจสอบจาก
p ถึง 100 หมายเลข
นั่นจะเป็นวงรอบนอกของเรา
เรากำลังจะสร้าง ตัวแปรสำหรับตัวนับวงในของเรา
นี่คือที่ที่เราตรวจสอบ ไพรม์ก่อนหน้าของเรา
อันที่จริงเราจะไม่เริ่มต้นมัน ที่นี่เราจะเริ่มต้นในลูป
เรากำลังจะสร้างอาร์เรย์ของเรา ซึ่งจะเป็นจำนวนเต็มของจำนวนเฉพาะ
และมันจะเป็นขนาด 50
และเราจะไม่เริ่มต้น ให้เป็นอะไรก็ได้ยกเว้น 0 สำหรับตอนนี้
แล้วเราจะสร้าง ดัชนีไพรม์ ซึ่งจะช่วยเราข้ามเลขคู่ทั้งหมดของเรา
และ เราจะตั้งมันเป็น 2
ตัวแปรนี้กำลังเกิดขึ้นจริง เพื่อให้แน่ใจว่าเราเริ่มต้นที่ดัชนีที่ถูกต้องเพราะเรากำลังจะไป
เพื่อฮาร์ดโค้ดตัวเลข 2 ตัวแรก
นั่นคือสิ่งที่เราจะทำก่อน
เรากำลังจะไปฮาร์ดโค้ด จำนวนเฉพาะ 2 ตัวแรกของเรา
นี่คือวิธีที่เราสามารถเข้าถึงอาร์เรย์ได้
เรารู้วิธีสร้างอาร์เรย์ในบรรทัด 10 คุณเพียงแค่ระบุประเภทข้อมูลตามด้วยชื่อแล้วใน
วงเล็บเหลี่ยมเราระบุขนาด
แล้วเราก็เริ่มต้น ทุกอย่างเป็น 0 นี่คือคุณลักษณะ
C99 ที่เราสามารถทำได้
และเพื่อกำหนดข้อมูลให้กับอาร์เรย์ ฉันสามารถพูดชื่ออาร์เรย์แล้วตามด้วยค่าดัชนี
จำไว้ว่าอาร์เรย์เป็น 0 ตาม
ผมจะพูดว่าไพรม์ซับ-0
และจำนวนเฉพาะตัวแรกจะเป็น 2
2 เป็นจำนวนเฉพาะตัวแรก
จำนวนเฉพาะตัวที่สองคือ จะเท่ากับ 3
ด้วยวิธีนี้ฉันมีไพรม์ ตัวเลขที่ก่อนหน้านี้ฉันสามารถทดสอบเพื่อหาจำนวนเฉพาะเพิ่มเติมได้
และตอนนี้การวนรอบของเราก็มาถึง
เราต้องการภายนอกสำหรับ วนซ้ำที่ผ่านตัวเลขทั้งหมดตั้งแต่
5 ถึง 100
เรารู้ว่า 4 ไม่ใช่จำนวนเฉพาะ ดังนั้นฉันเพิ่งเริ่มต้นที่ 5
เราก็บอกว่า 4 p เท่ากับ 5, p is น้อยกว่าหรือเท่ากับ 100 แล้วเราจะข้ามเลขคู่
เลยจะบอกว่า p เท่ากับ p บวก 2
เราไม่จำเป็นต้องดูตัวเลขใดๆ นั่นจะเป็นวงรอบนอกของเรา
และอีกครั้งคุณควรจะ การทดสอบในขณะที่คุณกำลังจะไป
ตอนนี้เรากำลังจะไปตั้งค่า ขึ้นตัวแปรบูลีนซึ่งจะบอกเราว่า
เราพบจำนวนเฉพาะ
นี่คือที่ที่ฉันสามารถใช้บูล และฉันจะสร้างตัวแปรโลคัลบูลีนเป็นไพรม์
ฉันจะได้เริ่มต้นนั้น ที่พูดเป็นความจริงเพราะฉันจะตั้งค่าเป็นเท็จถ้าฉันได้
ผ่านรายการของจำนวนเฉพาะที่สร้างไว้ก่อนหน้านี้ทั้งหมดหรือ
ฉันได้จำนวนเฉพาะตัวล่าสุดแล้ว และต้องแน่ใจว่าไม่ใช่รากที่สอง
ไพรม์ก็จะเท่ากับ เท่ากับ true สำหรับการวนซ้ำแต่ละครั้งตั้งแต่
5 ถึง 100 การข้าม 2
ตอนนี้วงในของฉันกำลังจะไป ผ่านจำนวนเฉพาะทั้งหมดที่เราได้สร้างไว้ก่อนหน้านี้
ทำให้เราไม่ได้ไปดีกว่า มากกว่าสแควร์รูทของ I
ดังนั้นเราจะผ่านทั้งหมด ตัวเลขจนกว่าเราจะไปถึงรากที่สอง, นั่นอาจเป็นเงื่อนไข
x ของเรา
พวกเรากำลังจะออกไปเช่นกัน ถ้าเราพบจำนวนเฉพาะ
เราจะบอกว่าถ้าเป็นไพรม์ เป็นจริงและเราผ่านขีดจำกัดของเราแล้ว
ซึ่งจะเป็น p หารด้วยจำนวนเฉพาะย่อย I มากกว่าหรือเท่ากับจำนวนเฉพาะย่อย
I
แล้วเราจะบวก บวก I คือตัวแปรควบคุมลูปของเรา
นี่คือ .จริงๆ กุญแจสู่อัลกอริทึม
เลยจะพยายาม ค้นหาจำนวนเฉพาะทั้งหมดของเราตั้งแต่
5 ถึง 100 ข้ามเลขคู่
แล้วในวงในของเรา เราคือ จะเริ่มต้นที่ 1 เราจะไปให้สุดจนกว่าจะตั้งตัวได้
เป็นจำนวนเฉพาะเป็นจริงหรือเราบรรลุเงื่อนไขทางออกแล้ว ซึ่งก็คือ จำนวน p หารด้วยไพรม์ sub-I
มากกว่าไพรม์ sub-I และนั่นคือ โดยพื้นฐานแล้วจะลงท้ายด้วยการสร้างของเราเมื่อเราพบสแควร์รูทเพราะนั่นคือ เงื่อนไขอื่นของอัลกอริทึม
ถ้านั่นคือวงของเรา ข้างใน ของวงของเรา เราจะตรวจสอบหาจำนวนเฉพาะ
วิธีที่จำนวนเป็นจำนวนเฉพาะ คือคุณหารมันด้วยตัวเลข
และถ้าคุณไม่มี 0 ถ้าอย่างนั้นคุณก็ไปได้ดี
ดังนั้นคุณสามารถทำ p mod ไพรม์ sub-I เท่ากับ 0
และถ้าเป็นอย่างนั้นจริง คุณก็ไม่มีจำนวนเฉพาะ
เพื่อให้คุณสามารถตั้งค่า บูลีนเท่ากับเท็จ
และนั่นคือสิ่งที่เราทำ สำหรับวงทั้งหมดเพราะสิ่งที่เราทำคือเรากำลังจะไป
เพื่อตั้งค่าบูลีนเป็นเท็จ
และนั่นจะบอกเราว่าเราไม่ได้ หาจำนวนเฉพาะ เราจึงไม่ต้องการบวก
p เข้าไปในอาร์เรย์ของจำนวนเฉพาะ
โอเค สิ่งสุดท้ายที่ต้องทำคือเราก็แค่ ตรวจสอบว่าบูลีนถูกตั้งค่าเป็น true หรือไม่ หากตั้งค่าเป็น
true เราต้องการกรอกข้อมูลในอาร์เรย์ของเรา
เราต้องการเพิ่มลงในอาร์เรย์ เราก็เลย การเพิ่มอาร์เรย์ที่เราพบว่าเป็นจำนวนเฉพาะ
เราก็แค่บอกว่าจำนวนเฉพาะและ แล้วเราจะบอกว่าดัชนีไพรม์
เพราะจำไว้ นี่แหละคือตัว ที่แสดงโดยดัชนีสำหรับตำแหน่งที่เราต้องการใส่ลงไป
อาร์เรย์ซึ่งเราต้องการเริ่มต้นที่องค์ประกอบ 3 ซึ่งเป็นดัชนี 2
เราเลยอยากแน่ใจว่าเราใส่มันเข้าไป ตำแหน่งที่ถูกต้องในอาร์เรย์
และเราตั้งค่าเป็น p เพราะ p เป็นจำนวนเฉพาะที่ เราพบเพราะจำไว้ว่านี่คือวงรอบนอก
เรากำลังพยายามตรวจสอบว่า นั่นคือจำนวนเฉพาะ
เราเริ่มตี 5
เราบอกว่าถ้า 5 จะเป็นจำนวนเฉพาะ if เราสามารถไปที่ตัวเลขเหล่านี้เริ่มต้นที่ 1 แล้วเปรียบเทียบกับใด
ๆ จำนวนเฉพาะก่อนหน้า และถ้ามันหารด้วย 0 ไม่ลงตัว เราก็ได้ และ
เราต้องทำอย่างนั้นเพื่อทุกสิ่ง
แล้วสิ่งสุดท้ายที่เรา สิ่งที่ต้องทำคือเราแค่ต้องการเพิ่มดัชนีไพรม์นั้น
ครั้งหน้าเราจะเจอไพรม์ หมายเลข เราอยู่ในดัชนีที่ถูกต้อง
และนั่นก็คือ
และนี่คือทั้งหมด อัลกอริธึมในการหาจำนวนเฉพาะ
ดังนั้นคุณต้องการบันทึกและสร้าง ตรวจสอบให้แน่ใจว่าทุกอย่างเรียบร้อยดี
ดี.
เลยชอบบวกเท็จจริง รวมค่าบูลมาตรฐานด้วย
อย่าลืมว่า
แล้วสิ่งสุดท้ายที่เรา ต้องทำคือเราต้องพิมพ์เลขเฉพาะออกมา
เราก็มี for loop ธรรมดาๆ ได้
และเราจะพิมพ์มัน ทั้งหมดอยู่ในบรรทัดเดียวกัน ดังนั้นเราจะไม่เพิ่มการป้อนบรรทัด
สิ่งที่เราจะทำคือ เราจะสร้างตัวอย่างตัวแปรควบคุมลูปของเราอีกครั้งเป็น
0 I
เราจะไปให้สุดทาง ดัชนีไพรม์ ซึ่งจะเป็นขนาดของทุกอย่างในอาร์เรย์
แล้วพิมพ์ออกมาในบรรทัดเดียว เปอร์เซ็นต์ I หรือ
d และไพรม์ sub-I
และในตอนท้ายสุด เราจะเพิ่มฟีดบรรทัด
บางอย่างเช่นที่มีเครื่องหมายอัฒภาค
แต่อีกครั้ง สิ่งที่จะ แจ้งให้ทราบในโปรแกรมนี้
ขั้นแรกให้สังเกตการเยื้อง บล็อกทั้งหมดเยื้อง
บางครั้งเราใช้วงเล็บเมื่อเรา มีมากกว่าหนึ่งคำสั่งในบล็อกของเรา
บางครั้งเราก็ไม่มี
ในนี้ if คำสั่งใน line 25 เราไม่ได้ใช้วงเล็บ
สำหรับลูปควรกลายเป็น ค่อนข้างเป็นธรรมชาติในขณะนี้
จริงๆแล้วสิ่งที่คุณต้องการได้รับจาก งานนี้คืออาร์เรย์
เรากำลังสร้างอาร์เรย์ที่เรียกว่าไพรม์ ตั้งค่าขนาด 50 เริ่มต้นทุกอย่างเป็น 0
จากนั้นเราจะตั้งค่าแรก 2 องค์ประกอบถึง 2 และ
3 แล้วอัลกอริธึมทั้งหมดนี้จาก 19 ถึง บรรทัดที่ 32 กำลังกำหนดว่ามันเป็นจำนวนเฉพาะหรือไม่โดยดูที่อาร์เรย์
ในจำนวนเฉพาะก่อนหน้า
และยังกระโดดออกมาเมื่อคุณ มากกว่ารากที่สอง
และอีกครั้งที่คุณเห็นจำนวนมากของ วงเล็บเหลี่ยมที่นี่เพื่อเข้าถึงอาร์เรย์และกำหนดค่า
สำหรับอาร์เรย์และทุกอย่าง ค่อนข้างตรงไปตรงมา
มาสร้างสิ่งนี้กันเถอะ และดูว่าเกิดอะไรขึ้น
เราไม่มีคำเตือนไม่มีข้อผิดพลาด
ถ้าเรารันสิ่งนี้สิ่งที่คุณเห็น คือเอาต์พุต คือจำนวนเฉพาะทั้งหมดถึง
100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 เป็นต้น
ทั้งหมดนี้เป็นจำนวนเฉพาะ
และจำนวนเฉพาะคือสิ่งที่ เป็นเพียงปัจจัยหนึ่งเท่านั้น
เอาไปแบ่งอย่างอื่นไม่ได้ และไม่มีเศษเหลือ
ดังนั้น 97 ตัวประกอบเพียง 2 ตัวที่ เข้าไปที่ 1 กับ 97
ดังนั้นอีกครั้งโปรแกรมด่วนเล็ก ๆ น้อย ๆ ที่ดี
ฉันจะให้วิธีแก้ปัญหา
คุณสามารถวิเคราะห์ได้
แต่ประเด็นสำคัญอีกครั้งทุกอย่าง เกี่ยวกับอาร์เรย์และบูลมาตรฐานที่ฉันใช้ด้วยว่า
อนุญาตให้เราสร้างประเภทข้อมูลบูลีนโดยไม่ต้องขีดล่างตัวพิมพ์ใหญ่
b และยังช่วยให้คุณใช้ค่าเท็จจริงแทน 1 และ 0
หวังว่านี่จะช่วยได้ ขอขอบคุณ.