Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Поправки к коду реализаций
Нет описания правки
Строка 17:
=Реализации=
В приведённых ниже реализациях предприняты следующие шаги, направленные на оптимизацию вычислений:
* Флаги «простое\составное» хранятся упакованными в массив битов (<code>vector<bool></code> для С++, <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); на выходе значения выдаются в заданном целочисленном типе.
Строка 24:
 
==[[w:C++|C++]]==
Простые числа могут вычисляться для любого целочисленного типа T; имеет смысл отдавать предпочтение беззнаковым (<code>unsigned</code>) типам. Результирующая последовательность может иметь тип <code>std::vector<T></code>, либо <code>std::list<T></code>, либо другой, поддерживающий методы очистки (<code>clear</code>) и добавления элементов в конец (<code>push_back</code>).
 
<source lang="cpp">
// atkin_sieve.hpph
#include <vector>
 
 
namespace AtkinSieve {
voidstd::vector<bool> getPrimesUpTo (unsigned const limit, Sequence &primes) {;▼
template < typename Sequence >
}
▲ void getPrimesUpTo (unsigned const limit, Sequence &primes) {
 
// Очистка результирующей последовательности
 
primes.clear();
#include// "atkin_sieve.hpp"cpp▼
// Числа 2 и 3 — заведомо простые▼
#include "atkin_sieve.h"
if (limit > 2u)▼
 
primes.push_back(2u);▼
 
else▼
std::vector<bool> AtkinSieve::getPrimesUpTo (unsigned const limit) {
return;▼
// Предварительное просеивание▼
if (limit > 3u)▼
std::vector<bool> sieve(limit);
primes.push_back(3u);▼
for (unsigned long long y2x2 = 1ull, dy2dx2 = 3ull, n; y2x2 < limit; y2x2 += dy2dx2, dy2dx2 += 2ull) {▼
else
for (unsigned numberlong long y2 = 5u1ull, dy2 = 3ull, n; numbery2 < limit; y2 += dy2, dy2 +number= 2ull) {▼
return;// n = 4x² + y²
▲ // Предварительное просеивание
std::vector<bool> sieve n = (limit);x2 << 2ull) + y2;
for (unsigned long long x2if (n <= 1ull,limit dx2&& =(n 3ull;% x212ull <== limit;1ull x2|| +=n dx2,% dx212ull +== 2ull5ull))
▲ primes sieve[n].push_backflip(3u);
▲ for (unsigned long long y2 = 1ull, dy2 = 3ull, n; y2 < limit; y2 += dy2, dy2 += 2ull) {
// n = 4x3x² + y²
n -= (x2 << 2ull) + y2;
if (n <= limit && (n % 12ull == 1ull || n % 12ull == 5ull)7ull)
sieve[n].flip();▼
// n = 3x² - y² (при x > y)▼
▲ return;if (x2 > y2) {
n -= y2 << 1ull;▼
if (n <= limit && n % 12ull == 11ull)▼
sieve[n].flip();
// n = 3x² + y²
n -= x2;
if (n <= limit && n % 12ull == 7ull)
▲ sieve[n].flip();
▲ // n = 3x² - y² (при x > y)
if (x2 > y2) {
▲ n -= y2 << 1ull;
▲ if (n <= limit && n % 12ull == 11ull)
sieve[n].flip();
}▼
}
▲ else}
// Все числа, кратные квадратам, помечаются как составные
unsigned r = 5u;▼
unsigned r = 5u;
for (unsigned long long r2 = r * r, dr2 = (r << 1ull) + 1ull; r2 < limit; ++r, r2 += dr2, dr2 += 2ull)
if (sieve[r])
for (unsigned long long mr2 = r2; mr2 < limit; mr2 += r2)
sieve[mr2] = false;
// Числа 2 и 3 — заведомо простые
// Занесение чисел в результирующую последовательность
▲ if (limit > 2u)
▲ for (unsigned number = 5u; number < limit; ++number)
if (sieve[number2u]) = true;
▲ if (limit > 3u)
primes.push_back(number);▼
▲ unsigned rsieve[3u] = 5utrue;
}
return sieve;
}
</source>
Строка 82 ⟶ 77 :
// main.cpp
#include <iostream>
#include <vector>
 
▲#include "atkin_sieve.hpp"
 
#include "atkin_sieve.h"
 
typedef std::vector<unsigned> Sequence;
 
int main () {
std::vector<bool> primes = AtkinSieve::getPrimesUpTo(100u, primes); // Вычисление простых чисел ≤ 100▼
Sequence primes;
▲ AtkinSieve::getPrimesUpTo(100u, primes); // Вычисление простых чисел ≤ 100
// Вывод последовательности
for (Sequence::const_iteratorunsigned iteratornumber = primes.begin()2u; iteratornumber !=< primes.endsize(); ++iteratornumber)
std::coutif << *iterator << ' ';(primes[number])
▲ std::cout << number << }' ';
return 0;
}
Строка 100 ⟶ 92 :
 
==[[w:Java|Java]]==
Простые числа вычисляются для типа <code>int</code>. Результирующая последовательность должна иметь тип, реализующий интерфейс <code>List<Integer></code> (например, <code>ArrayList<Integer></code>).
<source lang="java">
// AtkinSieve.java
import java.util.BitSet;
import java.util.List;
 
 
public class AtkinSieve {
public static voidBitSet getPrimesUpTo (int limit, List<Integer> primes) {
BitSet sieve = new BitSet();▼
// Очистка результирующей последовательности
primes.clear();
▲ // Числа 2 и 3 — заведомо простые
if (limit > 2)
primes.add(2);
else
return;
if (limit > 3)
primes.add(3);
else
return;
// Предварительное просеивание
▲ BitSet sieve = new BitSet();
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) {
Строка 145 ⟶ 124 :
for (long mr2 = r2; mr2 < limit; mr2 += r2)
sieve.set((int)mr2, false);
▲ // Числа 2 и 3 — заведомо простые
// Занесение чисел в результирующую последовательность
forif (intlimit number = 5; number < limit;> ++number2)
if (sieve.getset(number2, true);
if (limit > primes.add(number3);
▲ primessieve.push_backset(2u3, true);
return sieve;
}
}
Строка 155 ⟶ 136 :
<source lang="java">
// Main.java
import java.util.ArrayListBitSet;
 
 
public class Main {
public static void main (String []args){
BitSet primes = AtkinSieve.getPrimesUpTo(100, primes); // Вычисление простых чисел ≤ 100▼
ArrayList<Integer> primes = new ArrayList<>();
▲ AtkinSieve.getPrimesUpTo(100, primes); // Вычисление простых чисел ≤ 100
// Вывод последовательности
for (int primenumber := 2; number < primes.length(); ++number)
Systemif (primes.out.formatget("%d ", primenumber));
▲ primesSystem.push_backout.format("%d ", number);
}
}
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Решето_Аткина