Eratosthenes Süzme Algoritması: Python, C++ Örnek E-posta

Eratosthenes Eleği en basit asal sayı eleğidir. Belirli bir limitteki tüm asal sayıları arayan bir Asal sayı algoritmasıdır. Birkaç asal sayı elekleri vardır. Örneğin Eratosthenes Eleği, Atkin Eleği, Sundaram Eleği vb.

Kelime "elek” maddeleri filtreleyen bir alet anlamına gelir. Böylece eleme algoritması Python ve diğer diller asal sayıları filtreleyen bir algoritmayı ifade eder.

Bu algoritma, asal sayıyı yinelemeli bir yaklaşımla filtreler. Filtreleme süreci en küçük asal sayıyla başlar. Asal, 1'den büyük ve yalnızca iki böleni olan doğal bir sayıdır, yani 1 ve sayının kendisi. Asal olmayan sayılara bileşik sayılar denir.

Eratosthenes yönteminin süzgecinde önce küçük bir asal sayı seçiliyor ve bunun katları filtreleniyor. İşlem belirli bir aralıktaki bir döngüde çalışır.

Örneğin:

Sayı aralığını 2'den 10'a kadar alalım.

Eratosthenes Süzgecini uyguladıktan sonra 2, 3, 5, 7 asal sayılarının listesini üretecektir.

Eratosthenes'in Algoritma Eleği

İşte Eratosthenes Eleğinin algoritması:

) 1 Adım 2'den verilen n aralığına kadar sayıların bir listesini oluşturun. En küçük ve ilk asal sayı olduğu için 2 ile başlıyoruz.

) 2 Adım Listedeki en küçük sayıyı seçin, x (başlangıçta x eşittir 2), listede gezinin ve seçilen sayıların tüm katlarını işaretleyerek karşılık gelen bileşik sayıları filtreleyin.

) 3 Adım Daha sonra listedeki bir sonraki asal sayıyı veya işaretlenmemiş en küçük sayıyı seçin ve 2. adımı tekrarlayın.

) 4 Adım X'in değeri n'nin karekökünden küçük veya ona eşit olana kadar önceki adımı tekrarlayın (x<=).

Not: Matematiksel akıl yürütme oldukça basittir. Sayı aralığı n şu şekilde çarpanlara ayrılabilir:

n=a*b

Yine n =*

= (faktör daha küçük ) * (faktör şundan büyük: )

Yani en az bir tanesi asal faktörler veya her ikisi de <= olmalıdır. Böylece, geçiş yeterli olacak.

) 5 Adım Bu dört adımdan sonra kalan işaretlenmemiş sayılar, verilen n aralığındaki tüm asal sayılar olacaktır.

Örnek:

Bir örnek alalım ve nasıl çalıştığını görelim.

Bu örnekte 2'den 25'e kadar asal sayıların listesini bulacağız. Yani n=25.

) 1 Adım İlk adımda n=2 seçtiğimiz için 25'den 25'e kadar sayıların bir listesini alacağız.

) 2 Adım Daha sonra listedeki en küçük sayı olan x'i seçiyoruz. Başlangıçta x=2 en küçük asal sayıdır. Daha sonra listeyi dolaşıp 2'nin katlarını işaretliyoruz.

Verilen n değeri için 2'nin katları: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Not: Mavi renk seçilen sayıyı, pembe renk ise elenen katları belirtir

) 3 Adım Daha sonra bir sonraki en küçük işaretsiz sayı olan 3'ü seçiyoruz ve 3'ün katlarını işaretleyerek son adımı tekrarlıyoruz.

) 4 Adım 3. adımı x= olana kadar aynı şekilde tekrarlıyoruz. veya 5.

) 5 Adım Geriye kalan işaretlenmemiş sayılar 2'den 25'e kadar olan asal sayılar olacaktır.

sözde kod

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

Eratostenes Eleği C/C++ kod örneği

#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;
} 

Çıktı:

2 3 5 7 11 13 17 19 23

Eratosthenes Elekleri Python Program Örneği

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)

Çıktı:

2
3
5
7
11
13
17
19
23

Parçalı Elek

Tam sayı aralığında bir döngü yürütmek için Eratosthenes Eleğinin gerekli olduğunu gördük. Bu nedenle sayıları saklamak için O(n) bellek alanına ihtiyaç duyar. Çok geniş bir aralıktaki asal sayıları bulmaya çalıştığımızda durum karmaşıklaşıyor. Daha büyük bir n'ye bu kadar büyük bir bellek alanı ayırmak mümkün değildir.

Algoritma bazı yeni özellikler eklenerek optimize edilebilir. Fikir, sayı aralığını daha küçük parçalara bölmek ve bu parçalardaki asal sayıları tek tek hesaplamaktır. Bu, alan karmaşıklığını azaltmanın etkili bir yoludur. Bu yönteme bir bölümlü elek.

Optimizasyon aşağıdaki şekilde sağlanabilir:

1. 2'den XNUMX'ye kadar asal sayıları bulmak için basit bir elek kullanın ve bunları bir dizide saklayın.
2. [0…n-1] aralığını en fazla birden fazla boyut segmentine bölün
3. Her bölüm için, bölüm boyunca yineleyin ve 1. adımda bulunan asal sayıların katlarını işaretleyin. Bu adım, O('yi gerektirir.) maks.

Normal elek O(n) yardımcı bellek alanına ihtiyaç duyarken, bölümlü elek O(), büyük bir n için büyük bir gelişmedir. Yöntemin bir dezavantajı da vardır çünkü zaman karmaşıklığını iyileştirmez.

Karmaşıklık Analizi

Uzay Karmaşıklığı:

Eratosten algoritmasının basit elemesi O(n) bellek alanı gerektirir. Ve parçalı elek gerektirir
O() yardımcı alan.

Zaman Karmaşıklığı:

Düzenli bir eratosthenes eleme algoritmasının zaman karmaşıklığı O(n*log(log(n)))'dir. Bu karmaşıklığın ardındaki mantık aşağıda tartışılmaktadır.

Belirli bir n sayısı için, bileşik bir sayıyı (yani asal olmayan sayıları) işaretlemek için gereken süre sabittir. Yani döngünün çalışma sayısı şuna eşittir:

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

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

Asal sayıların toplamının harmonik ilerlemesi log(log(n)) olarak çıkarılabilir.

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

Yani, zaman karmaşıklığı şu şekilde olacak:

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

= n * log(log(n))

Böylece zaman karmaşıklığı O(n * log(log(n)))

Daha sonra şunları öğreneceksiniz: Pascal Üçgeni

ÖZET

• Eratosten Süzgeci belirli bir üst sınırdaki asal sayıları filtreler.
• Asal sayıların filtrelenmesi en küçük asal sayı olan “2”den başlar. Bu yinelemeli olarak yapılır.
• Yineleme, n'nin kareköküne kadar yapılır; burada n, verilen sayı aralığıdır.
• Bu tekrarlardan sonra geriye kalan sayılar asal sayılardır.