Решето Эратосфена

Сам алгоритм не такой шустрый как др. но создает ценный массив p[].

С ним, например, можно не только проверять простоту, но и факторизировать за O от ответа

void fact(int n){
    while(n>1){
        cout<<p[n]<<' ';
        n/=p[n];
    }
}

GeorgeeChebanov, по-мойму реализация неверная. Я так понимаю, ты пытался реализовать тот алгоритм, который А.Лопатин на сборах когда-то рассказывал? Дело в том, что там существенную роль играл сам массив p[], благодаря информации из него каждое число вычеркивалось не более одного раза, и получалась линейная асимптотика.
У тебя же массив p[] в общем-то и не используется в алгоритме, т.е. твой алгоритм я бы переписал так:

vector<char> prime (n+1, true);
vector<int> primes;
for (int i=2; i<=n; ++i) {
    if (prime[i])
        primes.push_back (i);
    for (size_t j=0; j < primes.size() && i * primes[j] <= n; ++j)
        prime[ i * primes[j] ] = false;
}

У меня баальшие сомнения, что он правда работает за линейное время.

Стопроцентно правильный алгоритм можно прочитать здесь. Интересно только, кто его первооткрыватель. Я тоже порыл в Интернете, и тоже не нашёл именно этого алгоритма. Есть очень близкие по идее алгоритмы, но такой поразительной простоты ни у одного из линейных решёт нет. Неужто открытие Лопатина?..

Определение проблемы
Для начала, вспомним, что существует так называемоерешето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
    int primesCount = 0;
    int sqrt_n = (int)sqrt((double)n);
    for (int i = 2; i <= n; ++i) {
        if (!notPrime[i]) {
            primes[primesCount++] = i;
            if (i <= sqrt_n) {
                for (int j = i * i; j <= n; j += i) {
                    notPrime[j] = true;
                }
            }
        }
    }
    return primesCount;
}

Почему решето работает не за линейное время? Потому что одно число в нем может вычеркиваться несколько раз (во внутреннем цикле) . Если добиться, чтобы каждое число вычеркивалось не более одного раза, то, очевидно, алгоритм будет линейным.
Решение
Чтобы сделать это, нам понадобится заменить массив

notPrime[]

на массив

int leastPrime[MAXN + 1]

.

leastPrime[x]

будет хранить индекс минимального простого числа в

primes[]

, на которое делится x. Очевидно, что

primes[leastPrime[x]] = x

для простого x. Также, вместо того чтобы вычеркивать числа вида

k * i,

где i - простое, будем вычеркивать числа вида

 primes[k] * i

, где i - это любое число, а

primes[k] <= primes[leastPrime[i]]

:

int leastPrime[MAXN + 1];
int primes[MAXN];
 
int advancedSieve(int n) {
    int primesCount = 0;
    for (int i = 2; i <= n; ++i) {
        if (!leastPrime[i]) {
            primes[primesCount++] = i;
            leastPrime[i] = primesCount;
        }
        for (int j = 0; j < leastPrime[i]; ++j) {
            int t = primes[j] * i;
            if (t <= n) leastPrime[t] = j + 1;
            else break;
        }
    }
    return primesCount;
}

Так как любое составное число однозначно представимо в виде

primes[k] * i,

где

primes[k] <= primes[leastPrime[i]],

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

Что читали на сборах я не знаю.

Мне это примерно в такой реализации объясняли в Зимней компьютерной школе (параллель С+).

Ыыыы
Он не может работать быстрее логически. Подумай разумно. Там линейно, тут больше гораздо.
Тогда нужно писать вот так,вместо +, использовать умножить,и это ускорит во много раз твою программу.

int n = (int)1e7;
vector <bool> prime(n+1,true);
for(int i=2;i*i<=n;i++)
    if(prime[i])
        for(int j=i*i;j<=n;j+=i)
            prime[j]=0;

А... Тогда понятно Зачем тогда Линейный алгоритм
Я не пробовал,надо будет проверить
Сейчас проверю и скажу мой отчёт
Буду проверять на Delphi, там точное время узнаю.
Проверять буду для 4e7 = 40 000 000 .

vectror<bool> сокращает память не в 4, а в 32 раза, потому что внутренне он реализован так, чтобы хранить информацию в битах, а не байтах.