1 (изменено: teadrinker, 2009-07-29 19:17:38)

Тема: 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)
}
Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder