อัลกอริทึมของตะแกรง Eratosthenes: Python, C++ ตัวอย่าง

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

คำ "กระชอน” หมายความว่า ภาชนะที่ใช้กรองสาร ดังนั้นอัลกอริธึมตะแกรงใน Python และภาษาอื่นๆ หมายถึงอัลกอริทึมในการกรองจำนวนเฉพาะออก

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

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

ตัวอย่างเช่น:

ลองหาช่วงตัวเลขตั้งแต่ 2 ถึง 10 กัน

หลังจากใช้ตะแกรงของเอราทอสเทนีสแล้ว จะได้รายการของจำนวนเฉพาะ 2, 3, 5, 7

ตะแกรงอัลกอริทึมของ Eratosthenes

นี่คืออัลกอริทึมสำหรับตะแกรง Eratosthenes:

ขั้นตอน 1) สร้างรายการตัวเลขตั้งแต่ 2 ถึงช่วง n ที่กำหนด เราเริ่มต้นด้วย 2 เนื่องจากเป็นจำนวนเฉพาะที่เล็กที่สุดและเป็นจำนวนเฉพาะตัวแรก

ขั้นตอน 2) เลือกตัวเลขที่เล็กที่สุดในรายการ x (โดยเริ่มต้น x เท่ากับ 2) เลื่อนผ่านรายการและกรองตัวเลขประกอบที่สอดคล้องกันโดยทำเครื่องหมายตัวคูณทั้งหมดของตัวเลขที่เลือก

ขั้นตอน 3) จากนั้นเลือกจำนวนเฉพาะถัดไปหรือจำนวนต่ำสุดที่ไม่มีเครื่องหมายในรายการ และทำซ้ำขั้นตอนที่ 2

ขั้นตอน 4) ทำซ้ำขั้นตอนก่อนหน้าจนกระทั่งค่า x ควรน้อยกว่าหรือเท่ากับรากที่สองของ n (x<=).

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

n=ก*ข

อีกครั้ง n=*

= (ตัวประกอบน้อยกว่า ) * (ตัวประกอบที่มากกว่า )

ดังนั้นอย่างน้อยหนึ่งในนั้น ปัจจัยสำคัญ หรือทั้งสองอย่างจะต้องเป็น <=- จึงเดินทางข้ามไป. จะเพียงพอ

ขั้นตอน 5) หลังจากสี่ขั้นตอนเหล่านั้นแล้ว ตัวเลขที่เหลือที่ไม่ได้ทำเครื่องหมายจะเป็นจำนวนเฉพาะทั้งหมดบนช่วง n ที่กำหนด

ตัวอย่าง:

ลองยกตัวอย่างและดูว่ามันทำงานอย่างไร

สำหรับตัวอย่างนี้ เราจะค้นหารายการของจำนวนเฉพาะตั้งแต่ 2 ถึง 25 ดังนั้น n=25

ขั้นตอน 1) ในขั้นตอนแรก เราจะเลือกรายการตัวเลขตั้งแต่ 2 ถึง 25 เนื่องจากเราเลือก n=25

ขั้นตอน 2) จากนั้นเราเลือกจำนวนที่น้อยที่สุดในรายการ x เริ่มแรก x=2 เนื่องจากเป็นจำนวนเฉพาะที่น้อยที่สุด จากนั้นเราข้ามผ่านรายการและทำเครื่องหมายผลคูณของ 2

ผลคูณของ 2 สำหรับค่าที่กำหนดของ n คือ: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

หมายเหตุ สีฟ้าหมายถึงหมายเลขที่เลือก และสีชมพูหมายถึงผลคูณที่ตัดออก

ขั้นตอน 3) จากนั้นเราเลือกตัวเลขที่เล็กที่สุดถัดไปที่ไม่มีเครื่องหมาย ซึ่งก็คือ 3 และทำซ้ำขั้นตอนสุดท้ายโดยทำเครื่องหมายผลคูณของ 3

ขั้นตอน 4) เราทำซ้ำขั้นตอนที่ 3 ในลักษณะเดียวกันจนกระทั่ง x= หรือ 5

ขั้นตอน 5) ตัวเลขที่เหลือที่ไม่ได้ทำเครื่องหมายจะเป็นจำนวนเฉพาะจาก 2 ถึง 25

รหัสหลอก

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

ตะแกรง Eratosthenes C/C++ ตัวอย่างโค้ด

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
} 

Output:

2 3 5 7 11 13 17 19 23

ตะแกรงเอราทอสเธเนส Python ตัวอย่างโปรแกรม

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Output:

2
3
5
7
11
13
17
19
23

ตะแกรงแบ่งส่วน

เราได้เห็นแล้วว่าตะแกรงของเอราทอสเทนีสจำเป็นสำหรับการวนซ้ำผ่านช่วงจำนวนเต็ม ดังนั้น จึงต้องใช้พื้นที่หน่วยความจำ O(n) เพื่อจัดเก็บตัวเลข สถานการณ์จะซับซ้อนขึ้นเมื่อเราพยายามค้นหาจำนวนเฉพาะในช่วงขนาดใหญ่ ไม่สามารถจัดสรรพื้นที่หน่วยความจำขนาดใหญ่สำหรับ n ที่ใหญ่กว่าได้

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

การเพิ่มประสิทธิภาพสามารถทำได้ในลักษณะต่อไปนี้:

1. ใช้ตะแกรงธรรมดาหาจำนวนเฉพาะตั้งแต่ 2 ถึง และจัดเก็บไว้ในอาร์เรย์
2. แบ่งช่วง [0…n-1] ออกเป็นหลายขนาดได้มากที่สุด
3. สำหรับแต่ละส่วน ให้ทำซ้ำผ่านส่วนนั้นและทำเครื่องหมายผลคูณของจำนวนเฉพาะที่พบในขั้นตอนที่ 1 ขั้นตอนนี้ต้องใช้ O() สูงสุด

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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของอวกาศ:

ตะแกรงอัลกอริธึม Eratosthenes อย่างง่ายต้องใช้พื้นที่หน่วยความจำ O(n) และต้องใช้ตะแกรงแบ่งส่วน
O() พื้นที่เสริม

ความซับซ้อนของเวลา:

ความซับซ้อนของเวลาของตะแกรงปกติของอัลกอริทึมเอราโทสเทนีสคือ O(n*log(log(n))) เหตุผลเบื้องหลังความซับซ้อนนี้จะอธิบายไว้ด้านล่าง

สำหรับจำนวน n ที่กำหนด เวลาที่จำเป็นในการทำเครื่องหมายจำนวนประกอบ (กล่าวคือ จำนวนที่ไม่ใช่จำนวนเฉพาะ) จะเป็นค่าคงที่ ดังนั้น จำนวนครั้งที่ลูปทำงานจึงเท่ากับ

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 + …….∞)

ความก้าวหน้าฮาร์มอนิกของผลรวมของจำนวนเฉพาะสามารถหักเป็น log(log(n))

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = บันทึก(บันทึก(n))

ดังนั้นความซับซ้อนของเวลาจะเป็นดังนี้-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * บันทึก (บันทึก (n))

ดังนั้นความซับซ้อนของเวลา O(n * log(log(n)))

ต่อไปคุณจะได้เรียนรู้เกี่ยวกับ สามเหลี่ยมปาสคาล

สรุป

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