Данные код имеет оптимизацию по памяти. Так это сито сегментированное. Мне нужна оптимизация по времени.
WinForm
void simpleSieve(ulong limit, ArrayList prime)
{
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
for (ulong p = 2; p * p < limit; p++)
{
if (mark[p] == true)
{
for (ulong i = (ulong)(p * p); i < limit; i += (ulong)p)
mark[i] = false;
}
}
for (ulong p = 2; p < limit; p++)
{
if (mark[p] == true)
{
prime.Add(p);
richTextBox1.AppendText(p + " ");
}
}
}
void segmentedSieve(ulong n)
{
int limit = (int)(Math.Floor(Math.Sqrt(n)) + 1);
ArrayList prime = new ArrayList();
simpleSieve((ulong)limit, prime);
ulong low = (ulong)limit;
ulong high = (ulong)(2 * limit);
while (low < n)
{
if (high >= n)
high = n;
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
for (int i = 0; i < prime.Count; i++)
{
ulong loLim = ((ulong)Math.Floor((double)(low / (ulong)prime[i])) * (ulong)prime[i]);
if (loLim < low)
loLim += (ulong)prime[i];
for (ulong j = loLim; j < high; j += (ulong)prime[i])
mark[j - low] = false;
}
for (ulong i = low; i < high; i++)
if (mark[i - low] == true)
richTextBox1.AppendText(i + " ");
low = low + (ulong)limit;
high = high + (ulong)limit;
}
}
Console
static void simpleSieve(int limit,
ArrayList prime)
{
/
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
for (int p = 2; p * p < limit; p++)
{
if (mark[p] == true)
{
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
for (int p = 2; p < limit; p++)
{
if (mark[p] == true)
{
prime.Add(p);
Console.Write(p + " ");
}
}
}
static void segmentedSieve(int n)
{
int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);
ArrayList prime = new ArrayList();
simpleSieve(limit, prime);
int low = limit;
int high = 2*limit;
while (low < n)
{
if (high >= n)
high = n;
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
// primes in current range
for (int i = 0; i < prime.Count; i++)
{
int loLim = ((int)Math.Floor((double)(low /
(int)prime[i])) * (int)prime[i]);
if (loLim < low)
loLim += (int)prime[i];
for (int j = loLim; j < high; j += (int)prime[i])
mark[j-low] = false;
}
for (int i = low; i < high; i++)
if (mark[i - low] == true)
Console.Write(i + " ");
low = low + limit;
high = high + limit;
}
}
static void Main()
{
int n = 100;
Console.WriteLine("Primes smaller than " + n + ":");
segmentedSieve(n);
}
оптимизация по времени
- сколько сейчас и сколько надо? Как тестируете?