Викиучебник

Реализации алгоритмов/Решето Аткина: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Добавлен пример для C#; подкорректированы примеры использования для всех языков
Строка 17:
=Реализации=
В приведённых ниже реализациях предприняты следующие шаги, направленные на оптимизацию вычислений:
* Флаги «простое\составное» хранятся упакованными в массив битов (<code>vector<bool></code> для С++, <code>BitArray</code> для C#, <code>BitSet</code> для Java и т. п.), возвращаемый функцией. Значение ''n''-го бита ''true'' соответствует простому ''n'', ''false'' — составному.
* Умножение на степень двойки производится операцией побитового сдвига (''<<''). Например <code>a << 2</code> вместо <code>4 * a</code>.
* Для уменьшения риска переполнения вычисления ведутся в типе длинное целое (<code>unsigned long long</code> в C++, <code>long</code> в Java); на выходе значения выдаются в заданном целочисленном типе.
Строка 75:
Пример использования:
<source lang="cpp">
// mainatkin_sieve_test.cpp
#include <iostream>
 
Строка 82:
 
int main () {
unsigned limit;
std::vector<bool> primes = AtkinSieve::getPrimesUpTo(100u); // Вычисление простых чисел ≤ 100▼
std::cin >> limit;
▲ std::vector<bool> primes = AtkinSieve::getPrimesUpTo(100ulimit); // Вычисление простых чисел ≤ 100
// Вывод последовательности
for (unsigned number = 2u; number <= primes.size()limit; ++number)
if (primes[number])
std::cout << number << ' ';
std::cout << '\n';
return 0;
}
</source>
 
==[[w:C_Sharp|C#]]==
<source lang="csharp">
// AtkinSieve.cs
using System;
using System.Collections;
 
 
public static class AtkinSieve
{
public static BitArray GetPrimesUpTo (int limit)
{
var sieve = new BitArray(limit + 1);
// Предварительное просеивание
for (long x2 = 1L, dx2 = 3L; x2 < limit; x2 += dx2, dx2 += 2L)
for (long y2 = 1L, dy2 = 3L, n; y2 < limit; y2 += dy2, dy2 += 2L)
{
// n = 4x² + y²
n = (x2 << 2) + y2;
if (n <= limit && (n % 12L == 1L || n % 12L == 5L))
sieve[(int)n] ^= true;
// n = 3x² + y²
n -= x2;
if (n <= limit && n % 12L == 7L)
sieve[(int)n] ^= true;
// n = 3x² - y² (при x > y)
if (x2 > y2)
{
n -= y2 << 1;
if (n <= limit && n % 12L == 11L)
sieve[(int)n] ^= true;
}
}
// Все числа, кратные квадратам, помечаются как составные
int r = 5;
for (long r2 = r * r, dr2 = (r << 1) + 1L; r2 < limit; ++r, r2 += dr2, dr2 += 2L)
if (sieve[r])
for (long mr2 = r2; mr2 < limit; mr2 += r2)
sieve[(int)mr2] = false;
// Числа 2 и 3 — заведомо простые
if (limit > 2)
sieve[2] = true;
if (limit > 3)
sieve[3] = true;
return sieve;
}
}
</source>
 
Пример использования:
<source lang="csharp">
// AtkinSieveTest.cs
using System;
using System.Collections;
using System.IO;
 
 
public static class AtkinSieveTest
{
public static void Main ()
{
int limit = int.Parse(Console.ReadLine());
var primes = AtkinSieve.GetPrimesUpTo(limit);
// Вывод последовательности
for (int number = 2; number <= limit; ++number)
if (primes[number])
Console.Write("{0} ", number);
Console.WriteLine();
}
}
</source>
Строка 133 ⟶ 207 :
}
</source>
 
Пример использования:
<source lang="java">
// MainAtkinSieveTest.java
import java.util.BitSet;
import java.util.Scanner;
 
 
public class MainAtkinSieveTest {
public static void main (String [] args) {
Scanner scanner = new Scanner(System.in);
BitSet primes = AtkinSieve.getPrimesUpTo(100); // Вычисление простых чисел ≤ 100▼
int limit = scanner.nextInt();
▲ BitSet primes = AtkinSieve.getPrimesUpTo(100limit); // Вычисление простых чисел ≤ 100
// Вывод последовательности
for (int number = 2; number <= primes.length()limit; ++number)
if (primes.get(number))
System.out.format("%d ", number);
System.out.println();
}
}
</source>
 
=См. также=
[[Реализации алгоритмов/Решето Сундарама|Решето Сундарама]]
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Решето_Аткина