Тема: AHK: Алгоритмы нахождения простых чисел до заданного целого числа
Следующие варианты кода сохраняют в текстовый файл строку, содержащую все простые числа до числа limit. Для наглядности в файл также выводится информация о количестве времени, понадобившемся для создания строки (без учёта времени записи в файл).
Решето Эратосфена.
limit = 1000000
FileDelete, %A_Desktop%\Prime%limit%.txt
StartTime := A_TickCount
Is_Prime := Prime_Erat(limit, quantity := 0)
Time := A_TickCount - StartTime
sec_msec := SubStr(Time/1000, 1, -3)
min_sec_msec := sec_msec >= 60 ? Floor((sec := SubStr(sec_msec, 1
, -4))/60) "." SubStr("00" . Mod(sec, 60), -1) . SubStr(sec_msec, -3) : sec_msec
FileAppend,
(
Проверено: %limit%
Найдено: %quantity%
Время: %min_sec_msec%
Сохранено: %A_Desktop%\Prime%limit%.txt
%Is_Prime%
), %A_Desktop%\Prime%limit%.txt
Run, %A_Desktop%\Prime%limit%.txt
Prime_Erat(limit, ByRef quantity) ; функция, возвращающая строку с простыми числами до limit
{
#NoEnv
SetBatchLines, -1 ; для скорости
; Необходимо провести вычёркивания кратных для всех простых чисел Prime, для которых
; Prime**2 <= limit. Вычисляем ближайшее снизу целое число к квадратному корню из limit
sqr_lim := Floor(Sqrt(limit))
Prime := 2 ; первое простое число
; Вместо того, чтобы создавать массив из натуральных чисел до limit, и вычёркивать составные,
; для экономии времени создадим массив из составных чисел. Не входящие в него
; целые в пределах limit будут простыми
While (Prime <= sqr_lim)
{
if !Composite%Prime% ; число, не входящее в массив — простое
{
Is_Prime .= Prime ", " ; запишем его сразу в строку, чтобы после не обращаться к нему повторно
quantity++ ; счётчик простых чисел
j := Prime * Prime
While (j <= limit)
{
Composite%j% := True ; создаём массив из составных чисел
j += Prime
}
}
Prime++
}
While (Prime <= limit) ; запишем в строку остальные простые числа (бОльшие, чем sqr_lim)
{
if !Composite%Prime%
{
Is_Prime .= Prime ", "
quantity++
}
Prime++
}
Return SubStr(Is_Prime, 1, -2)
}
Решето Аткина.
Без комментариев. Чтобы понять, как работает этот код, см. статью, источник, а также уточнение.
limit = 1000000
FileDelete, %A_Desktop%\Prime%limit%.txt
StartTime := A_TickCount
Is_Prime := Prime(limit, quantity := 0)
Time := A_TickCount - StartTime
sec_msec := SubStr(Time/1000, 1, -3)
min_sec_msec := sec_msec >= 60 ? Floor((sec := SubStr(sec_msec, 1
, -4))/60) "." SubStr("00" . Mod(sec, 60), -1) . SubStr(sec_msec, -3) : sec_msec
FileAppend,
(
Проверено: %limit%
Найдено: %quantity%
Время: %min_sec_msec%
Сохранено: %A_Desktop%\Prime%limit%.txt
%Is_Prime%
), %A_Desktop%\Prime%limit%.txt
Run, %A_Desktop%\Prime%limit%.txt
Prime(limit, ByRef quantity)
{
SetBatchLines, -1
Loop % limit
Is_Prime%a_index% := false
Is_Prime2 := Is_Prime3 := True
sqr_lim := Floor(Sqrt(limit)), x2 := 0
While (a_index <= sqr_lim)
{
i := a_index
x2 += 2 * i - 1, y2 := 0
While (a_index <= sqr_lim)
{
y2 += 2 * a_index - 1
n := 4 * x2 + y2
if (n <= limit) && (mod(n, 12) = 1 || mod(n, 12) = 5)
Is_Prime%n% := !Is_Prime%n%
n -= x2
if (n <= limit) && (mod(n, 12) = 7)
Is_Prime%n% := !Is_Prime%n%
n -= 2 * y2
if (i > a_index) && (n <= limit) && (mod(n, 12) = 11)
Is_Prime%n% := !Is_Prime%n%
}
}
i := 5
While (i <= sqr_lim)
{
if Is_Prime%i%
{
n := i * i
j := n
While (j <= limit)
Is_Prime%j% := false, j += n
}
i++
}
i := 2
While (i <= limit)
{
if Is_Prime%i%
{
Is_Prime .= i . ", "
quantity++
}
i++
}
Return SubStr(Is_Prime, 1, -2)
}