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

Содержимое удалено Содержимое добавлено
Нет описания правки
Строка 344:
name = "atkin_sieve_test"
path = "src/atkin_sieve_test.rs"
</source>
 
 
==[[w:Golang|Go]]==
<source lang="go">
package atkinsieve
 
import "math"
 
func AtkinSieve(limit uint) []bool {
// Инициализация решета
sqr_lim := uint(math.Sqrt(float64(limit)))
is_prime := make([]bool, limit+1)
is_prime[2] = true
is_prime[3] = true
 
// Предположительно простые — это целые с нечётным числом
// представлений в данных квадратных формах.
// x2 и y2 — это квадраты i и j (оптимизация).
var n uint
x2 := uint(0)
for i := uint(1); i <= sqr_lim; i++ {
x2 += 2*i - 1
y2 := uint(0)
for j := uint(1); j <= sqr_lim; j++ {
y2 += 2*j - 1
n = 4*x2 + y2
if (n <= limit) && (n%12 == 1 || n%12 == 5) {
is_prime[n] = !is_prime[n]
}
// n = 3 * x2 + y2;
n -= x2 // Оптимизация
if (n <= limit) && (n%12 == 7) {
is_prime[n] = !is_prime[n]
}
// n = 3 * x2 - y2;
n -= 2 * y2 // Оптимизация
if (i > j) && (n <= limit) && (n%12 == 11) {
is_prime[n] = !is_prime[n]
}
 
}
}
// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for i := uint(5); i <= sqr_lim; i++ {
if is_prime[i] {
n = i * i
for j := n; j <= limit; j += n {
is_prime[j] = false
}
}
}
return is_prime
}
</source>