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 Algoritmasının Süzülmesi

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

Eratosthenes Algoritmasının Süzülmesi

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<=Eratosthenes'in Algoritma Eleği).

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

n=a*b

Yine n =Eratosthenes'in Algoritma Eleği*Eratosthenes'in Algoritma Eleği

= (faktör daha küçük Eratosthenes'in Algoritma Eleği) * (faktör şundan büyük: Eratosthenes Algoritmasının Süzülmesi)

Yani en az bir tanesi asal faktörler veya her ikisi de <= olmalıdırEratosthenes'in Algoritma Eleği. Böylece, geçiş Eratosthenes'in Algoritma Eleğ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.

Eratosthenes'in Algoritma Eleği

) 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.

Eratosthenes Algoritmasının Süzülmesi

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.

Eratosthenes Algoritmasının Süzülmesi

) 4 Adım 3. adımı x= olana kadar aynı şekilde tekrarlıyoruz.Eratosthenes Algoritmasının Süzülmesi veya 5.

Eratosthenes Algoritmasının Süzülmesi

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

Eratosthenes Algoritmasının Süzülmesi

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 Parçalı Elek ve bunları bir dizide saklayın.
  2. [0…n-1] aralığını en fazla birden fazla boyut segmentine bölün Parçalı Elek
  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.Parçalı Elek) maks.

Normal elek O(n) yardımcı bellek alanına ihtiyaç duyarken, bölümlü elek O(Parçalı Elek), 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(Karmaşıklık Analizi) 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.