Задача, найти алгоритм, который выдает перечень простых чисел в интервале от 1 до n.

Насколько я понял, если отбросить вероятностные алгоритмы и поиск по массиву известных чисел, то вараинтов решения всего два.

Первый — прямолинейный, для каждого k (1<=k<=n) найти остаток от деления от всех чисел в интервале 1..sqrt(n). Алгоритм не требовательный к памяти, но работает медленно. Грубо — O(n * sqrt(n)).
Второй — решето Эратосфена.

Вопрос 1 — а каково быстродействие данного алгоритма (bigO)?

Самая тупая приходящая в голову реализация — завести список целых чисел от 1 до n, и выкидывать из него составные не подходит из за требований к хранению данного списка в памяти.

Вопрос 2 — возможна ли реализация решета Эратосфена менее требовательная к памяти?

Я погуглил, и нашел реализацию которая ищет простые числа, называется решетом Эратосфена, но imho таковой не является. Поправьте меня если я не прав:

    #include <stdafx.h>
#include "eratosthenes.h"

/*************************************************************************
Процедура заполняет массив P простыми числами меньшими n,
элемент массива является последним, если следующий за ним
элемент равен 0.
*************************************************************************/
void eratosthenessieve(const int& n, ap::integer_1d_array& p)
{
    bool c;
    int i;
    int j;
    int k;
    int r;
    double s;

    if( n>200 )
    {
        r = ap::trunc(n/(log(double(n))-2)+1);
    }
    else
    {
        r = ap::trunc(1.6*n/log(double(n))+1);
    }
    p.setbounds(1, r);
    p(1) = 1;
    p(2) = 2;
    p(3) = 3;
    i = 4;
    do
    {
        p(i) = 0;
        i = i+1;
    }
    while(i<=r);
    j = 3;
    k = 3;
    do
    {
        i = 2;
        s = sqrt(double(k));
        c = true;
        do
        {
            i = i+1;
            if( p(i)>s )
            {
                p(j) = k;
                j = j+1;
                c = false;
            }
        }
        while(ap::trunc(double(k)/double(p(i)))*p(i)!=k&&c);
        k = k+2;
    }
    while(k<=n);
}

Как я понял эту реализацию:
1. j — указатель на следующее простое число в массиве. Нужен для того, чтобы после нахождения очередного простого числа мы знали куда его вставлять в целевой массив.
2. k — кандидиат на простое число (все нечетные числа). Хм... насколько я понимаю, это только первый цикл решета, дальше мы должны идти с шагом 3, 5 ....
3. каждого кандидата (k) мы пробуем нацело поделить на одно из известных простых чисел (trunc(double(k)/double(p(i)))*p(i)) до тех пор пока квадрат очередного известного простого числа не превысит кандидата (if( p(i)>s )). Дальше искать просто смысла нет.

Вопрос 3 — и где же здесь реализация решета? IMHO, это реализация первого способа — тупого перебора. Или я не прав?