Algoritma yang paling terkenal untuk menemukan semua bilangan prima tidak lebih besar dari bilangan prima adalah saringan Eratosthenes . Ini berfungsi baik untuk angka hingga miliaran, mungkin hingga puluhan miliar, jika ditulis dengan rapi. Namun, semua orang yang suka bersenang-senang dengan bilangan prima tahu bahwa Anda selalu ingin memiliki sebanyak mungkin di tangan. Suatu ketika, untuk menyelesaikan satu masalah pada hackerrank, saya membutuhkan basis data dalam memori dari bilangan prima hingga seratus miliar. Dengan optimalisasi maksimum oleh memori, jika saringan Eratosthenes menyajikan angka ganjil dengan array bit, ukurannya akan sekitar 6 gigabyte, yang tidak sesuai dengan memori laptop saya. Ada modifikasi dari algoritma yang jauh lebih sedikit menuntut dalam memori (membagi rentang angka asli menjadi beberapa bagian dan memproses satu bagian pada satu waktu) -saringan Eratosthenes yang tersegmentasi , tetapi lebih sulit untuk diimplementasikan, dan seluruh hasilnya tidak akan masuk ke dalam memori. Di bawah ini, saya perhatikan algoritma yang hampir sesederhana saringan Eratosthenes, tetapi yang memberikan optimasi ganda oleh memori (yaitu, basis data prima hingga seratus miliar akan menempati sekitar 3 gigabytes, yang seharusnya sudah masuk ke dalam memori laptop standar).Untuk mulai dengan, kita ingat bagaimana saringan Eratosthenes bekerja: dalam array angka dari 1 hingga N, angka yang dapat dibagi dua dicoret, kemudian angka yang dapat dibagi 3, dan seterusnya. Angka yang tersisa setelah dicoret akan menjadi sederhana:2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 ...
Kode C #class EratospheneSieve
{
private bool[] Data;
public EratospheneSieve(int length)
{
Data = new bool[length];
for (int i = 2; i < Data.Length; i++) Data[i] = true;
for (int i = 2; i * i < Length; i++)
{
if (!Data[i]) continue;
for (int d = i * i; d < Length; d += i) Data[d] = false;
}
}
public int Length => Data.Length;
public bool IsPrime(int n) => Data[n];
}
Di laptop saya, ia menghitung hingga 15 miliar detik dan menghabiskan satu gigabyte memori.Algoritma yang akan kita gunakan disebut Wheel Factorization . Untuk memahami esensinya, kami menulis angka alami dengan tablet 30 buah berturut-turut: 0 1 2 3 4 5 ... 26 27 28 29
30 31 32 33 34 35 ... 56 57 58 59
60 61 62 63 64 65 ... 86 87 88 89
...
Dan coret semua angka yang dapat dibagi 2, 3, dan 5:. 1 . . . . . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29
. 31 . . . . . 37 . . . 41 . 43 . . . 47 . 49 . . . 53 . . . . . 59
. 61 . . . . . 67 . . . 71 . 73 . . . 77 . 79 . . . 83 . . . . . 89
...
Dapat dilihat bahwa pada setiap nomor baris dicoret pada posisi yang sama. Karena kita mencoret hanya nomor gabungan (dengan pengecualian, pada kenyataannya, dari angka 2, 3, 5), maka bilangan prima hanya dapat berada di posisi yang tidak ditandai.Karena ada delapan angka seperti itu di setiap baris, ini memberi kita ide untuk mewakili masing-masing tiga puluh angka dengan satu byte, masing-masing dari delapan bit yang akan menunjukkan kesederhanaan angka di posisi yang sesuai. Kebetulan ini tidak hanya indah secara estetika, tetapi juga sangat menyederhanakan penerapan algoritma!
Implementasi teknis
Pertama, tujuan kami adalah untuk mencapai seratus miliar, sehingga angka empat byte tidak dapat lagi dihilangkan. Karenanya, algoritme kami akan terlihat seperti ini:class Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
...
}
public bool IsPrime(long n)
{
...
}
...
}
Untuk kemudahan implementasi, kami akan membulatkan panjang ke nomor terdekat yang dapat dibagi 30. Kemudianclass Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length/30];
...
}
public long Length => Data.Length * 30L;
...
}
Selanjutnya, kita membutuhkan dua larik: satu menerjemahkan indeks 0..29 ke dalam nomor bit, yang kedua, sebaliknya, jumlah bit ke posisi tiga puluh. Menggunakan array ini dan sedikit aritmatika bit, kami membangun korespondensi satu-ke-satu antara bilangan asli dan bit dalam array Data. Untuk kesederhanaan, kami hanya menggunakan dua metode: IsPrime (n), yang memungkinkan Anda untuk mengetahui apakah bilangan prima, dan ClearPrime (n), yang menetapkan bit yang sesuai ke 0, menandai angka n sebagai senyawa:class Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
...
public bool IsPrime(long n)
{
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Perhatikan bahwa jika angka tersebut dapat dibagi 2, 3 atau 5, maka angka bit akan menjadi -1, yang berarti angka tersebut jelas merupakan gabungan. Baik dan, tentu saja, kami sedang memproses kasus khusus n <= 5.Sekarang, sebenarnya, algoritma itu sendiri, yang hampir secara harfiah mengulangi saringan Eratosthenes: public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
Dengan demikian, seluruh kelas yang dihasilkan:terlihat seperti ituclass Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Hanya ada satu masalah kecil: kode ini tidak berfungsi untuk angka yang lebih besar dari sekitar 65 miliar! Saat Anda mencoba memulainya dengan angka-angka seperti itu, program macet dengan kesalahan:Unhandled Exception: System.OverflowException: Array dimensions exceeded supported range.
Masalahnya adalah bahwa dalam c # array tidak dapat memiliki lebih dari 2 ^ 31 elemen (tampaknya karena implementasi internal menggunakan indeks array empat byte). Salah satu opsi adalah membuat, misalnya, array [] lama alih-alih array byte [], tetapi ini akan menyulitkan bit aritmatika sedikit. Untuk kesederhanaan, kita akan pergi ke arah lain, menciptakan kelas khusus yang mensimulasikan array yang diinginkan, memegang dua array pendek di dalamnya. Pada saat yang sama, kami akan memberinya kesempatan untuk menyelamatkan diri ke disk sehingga Anda dapat menghitung bilangan prima sekali, dan kemudian menggunakan database lagi: class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
...
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
...
}
}
Akhirnya, gabungkan semua langkah diversi terakhir dari algoritmaclass Wheel235
{
class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
using(FileStream stream = File.OpenRead(file))
{
long length = stream.Length;
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
stream.Read(firstBuffer, 0, firstBuffer.Length);
if(secondBuffer != null) stream.Read(secondBuffer, 0, secondBuffer.Length);
}
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
using(FileStream stream = File.OpenWrite(file))
{
stream.Write(firstBuffer, 0, firstBuffer.Length);
if (secondBuffer != null) stream.Write(secondBuffer, 0, secondBuffer.Length);
}
}
}
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private LongArray Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new LongArray(length / 30);
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public Wheel235(string file)
{
Data = new LongArray(file);
}
public void Save(string file) => Data.Save(file);
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Akibatnya, kami mendapat kelas yang dapat menghitung bilangan prima tidak melebihi seratus miliar dan menyimpan hasilnya ke disk (saya punya kode ini di laptop saya selama 50 menit; ukuran file yang dibuat sekitar 3 gigabyte, seperti yang diharapkan): long N = 100_000_000_000L;
Wheel235 wheel = new Wheel235(N);
wheel.Save("./primes.dat");
Dan kemudian baca dari disk dan gunakan: DateTime start = DateTime.UtcNow;
Wheel235 loaded = new Wheel235("./primes.dat");
DateTime end = DateTime.UtcNow;
Console.WriteLine($"Database of prime numbers up to {loaded.Length:N0} loaded from file to memory in {end - start}");
long number = 98_000_000_093L;
Console.WriteLine($"{number:N0} is {(loaded.IsPrime(number) ? "prime" : "not prime")}!");