Алгоритм Сундарама

@Мария922 · Регистрация: 05.12.2013

Author24 — интернет-сервис помощи студентам

Всем здрасти!!! помогите пожалуйста с прогой. Сформировать и напечатать одномерный массив А{ai} (i=1..N), где ai=i. В массиве А найти все простые числа используя алгоритм Сундарама и вывести их на экран

@Mikl___ · 15.12.2013, 13:07

Мария922,
а что это за чудо - алгоритм Сундарама? Показывай свои программные попытки, тогда поможем...

@Мария922 · 17.12.2013, 19:15 **[ТС]**

мало информации про этот Сундарама((( незнаю как сделать...

Charles Kludge · 17.12.2013, 21:10

http://ru.wikibooks.org/wiki/П... _Сундарама

ФедосеевПавел · 18.06.2020, 13:28

По ссылке Charles Kludge нашёл реализации решета Сундарама и пояснения алгоритма.
На C получается просто, с учётом пересчёта индексов массива, начинающихся от нуля, в то время, как для алгоритма начальный индекс равен единице

C

#include <stdio.h>
#include <stdlib.h>
 
#define _N_MAX_ 100
int main()
{
    //инициализация массива - все числа простые
    int a[_N_MAX_];
    int i,j,k;
    for(i=0; i<_N_MAX_; i++)
        a[i]=1;
    //реализация решета
    for(i=1; i+i+2*i*i<=_N_MAX_; i++)
        for(j=i; k=(i+j+2*i*j), k<=_N_MAX_; j++)
            a[k-1]=0;
    //вывод результатов
    printf("  1. 2\n");
    j=2;
    for(i=0; i<_N_MAX_; i++)
        if(a[i])
        {
            j++;
            printf("%3d. %d\n", j, 2*i+3);
        }
    return 0;
}

Далее, есть смысл усложнить вычисления индексов, но исключить инструкции умножения.

Индекс вычёркиваемого элемента равен
k=i+j+2ij
Самый первый элемент для нового значения i равен
ki=2i+2i²
Его приращение, по сравнению с предыдущим значением переменной i равно
Dki=2i+2i²-(2(i-1)+2(i-1)²)=2i+2i²-(2i-2+2i²-4i+2)=4i

Так же найдём приращения индекса вычёркиваемого элемента при приращении переменной j
Dk=(i+j+2ij)-(i+(j-1)+2i(j-1))=i+j+2ij-i-j+1-2ij+2i=1+2i

В итоге получим такой алгоритм

C

/*
решето Сундарама
*/
#include <stdio.h>
#include <stdlib.h>
 
#define _N_MAX_ 100
int main()
{
    //инициализация массива - все числа простые
    int a[_N_MAX_];
    int i;
    for(i=0; i<_N_MAX_; i++)
        a[i]=1;
    //реализация решета
    int ki=0;
    for(i=1; ki<=_N_MAX_; i++)
    {
        ki=ki+4*i;
        int k;
        int j;
        for(j=i, k=ki; k<=_N_MAX_; j++)
        {
            a[k-1]=0;
            k=k+1+2*i;
        }
    }
    //вывод результатов
    printf("  1. 2\n");
    int j=1;
    for(i=0; i<_N_MAX_; i++)
        if(a[i])
        {
            j++;
            printf("%3d. %d\n", j, 2*i+3);
        }
    return 0;
}

Это уже легко преобразуется в программу на ассемблере.
Можно ещё отметить, что в цикле по j само значение j не используется и этот цикл превращается в цикл с постусловием по переменной k.

Assembler

.486
.model flat, stdcall
option casemap :none
 
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\masm32.inc
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\masm32.lib
.data
        aszCrLf         db      0Dh, 0Ah, 0
        aszPressLeftAlt db      0Dh, 0Ah, 0Dh, 0Ah, "Press Left Alt to exit", 0
        aszResult       db      "%3d. %d", 0Dh, 0Ah, 0
        _N_MAX_         =       100
.data?
        hConsoleOutput  HANDLE  ?
        hConsoleInput   HANDLE  ?
        BufLen          dd      ?
        Buffer          db      1024 dup(?)
        A               db      _N_MAX_ dup(?)
.code
 
start   proc
 
        ; получение описателей ввода и вывода консоли
        invoke  GetStdHandle,   STD_INPUT_HANDLE
        mov     hConsoleInput,  eax
        invoke  GetStdHandle,   STD_OUTPUT_HANDLE
        mov     hConsoleOutput, eax
        ;очистка экрана
        invoke  ClearScreen
 
        ; //инициализация массива - все числа простые
        mov     ecx,    _N_MAX_                                 ; for(i=0; i<_N_MAX_; i++)
        lea     edi,    [A]
        mov     al,     1
        rep     stosb                                           ;   a[i]=1;
        ; //реализация решета
        lea     ebx,    [A]
        mov     ecx,    0                                       ; int ki=0;
        mov     esi,    1                                       ; for(i=1; ki<=_N_MAX_; i++)
        @@forI:                                                 ; {
                lea     ecx,    [ecx+4*esi]                     ;     ki=ki+4*i;
                lea     edi,    [ecx-1]                         ;     for(j=i, k=ki; k<=_N_MAX_; j++)
                @@forJ:                                         ;     {
                        mov     [ebx+edi],      byte ptr 0      ;         a[k-1]=0;
                        lea     edi,    [edi+2*esi+1]           ;         k=k+1+2*i;
                        cmp     edi,    _N_MAX_
                jb      @@forJ                                  ;     }
                inc     esi
                cmp     ecx,    _N_MAX_
        jbe     @@forI                                          ; }
        ; //вывод результатов
        invoke  wsprintf, ADDR Buffer, ADDR aszResult, 1, 2     ; printf("  1. 2\n");
        mov     [BufLen],       eax
        invoke  WriteConsole, hConsoleOutput, ADDR Buffer,\
                BufLen, ADDR BufLen, NULL
        mov     ebx,    1                                       ; int j=1;
        lea     esi,    [A]
        mov     edi,    0
        mov     ecx,    _N_MAX_                                 ; for(i=0; i<_N_MAX_; i++)
        @@for:
                cmp     byte ptr[esi],  0                       ;     if(a[i])
                jz      @f                                      ;     {
                        inc     ebx                             ;         j++;
                        push    ecx                             ;         printf("%3d. %d\n", j, 2*i+3);
                        push    ebx
                        lea     eax,    [2*edi+3]
                        invoke  wsprintf, ADDR Buffer, ADDR aszResult, ebx, eax
                        mov     [BufLen],       eax
                        invoke  WriteConsole, hConsoleOutput, ADDR Buffer,\
                                BufLen, ADDR BufLen, NULL
                        pop     ebx
                        pop     ecx
                @@:                                             ;     }
                inc     edi
                inc     esi
        loop    @@for
 
        ;ожидание нажатия Left Alt
        invoke  WriteConsole, hConsoleOutput, ADDR aszPressLeftAlt,\
                LENGTHOF aszPressLeftAlt - 1, ADDR BufLen, NULL
        @@WaitForLAlt:
                invoke  GetAsyncKeyState, VK_LMENU
                and     eax,    8000h
        jz      @@WaitForLAlt
        ;завершение программы
        invoke  ExitProcess, 0
start   endp
 
end start

К сожалению, исходник по ссылке Реализации алгоритмов/Решето Сундарама без описания понять труднее.
Видно, что инициализация массива производится сразу с учётом вычёркивания элементов, кратных трём. И вычисления начинаются с рассмотрения i=2, т.е. вычёркивания элементов, кратных пяти.
Далее - уже какие-то циклы, с учётом "таинственных" преобразований.

@Мария922 0 / 0 / 0 Регистрация: 05.12.2013 Сообщений: 5
		1
	Алгоритм Сундарама 15.12.2013, 11:43. Показов 708. Ответов 4 Метки нет (Все метки) Всем здрасти!!! помогите пожалуйста с прогой. Сформировать и напечатать одномерный массив А{ai} (i=1..N), где ai=i. В массиве А найти все простые числа используя алгоритм Сундарама и вывести их на экран 0

@Mikl___ Ушел с форума 16281 / 7605 / 1066 Регистрация: 11.11.2010 Сообщений: 13,618
	15.12.2013, 13:07	2
	Мария922, а что это за чудо - алгоритм Сундарама? Показывай свои программные попытки, тогда поможем... 0

@Мария922 0 / 0 / 0 Регистрация: 05.12.2013 Сообщений: 5
	17.12.2013, 19:15 [ТС]	3
	мало информации про этот Сундарама((( незнаю как сделать... 0

Charles Kludge Клюг 7674 / 3189 / 382 Регистрация: 03.05.2011 Сообщений: 8,380
	17.12.2013, 21:10	4
	http://ru.wikibooks.org/wiki/П... _Сундарама 2

	18.06.2020, 13:28