Тема: Решето Эратосфена
Отсутствует оптимизация за O(n)
Не забудьте добавить.
P.S Если нужно, могу написать код.
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Решето Эратосфена
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Отсутствует оптимизация за O(n)
Не забудьте добавить.
P.S Если нужно, могу написать код.
int *p,*a,n,k;
cin >> n;
p = new int[n+1]; // p[i] = min p-простое, i%p==0,i>=2
a = new int[n+1]; // a[0..k-1] - все простые [2..i);
for(int i=2;i<=n;i++)
p[i]=i;
k = 0; // количество простых in [2..i)
int i;
for(i=2;i<=n;i++){
if(p[i]==i)
a[k++]=i;
for(int j=0;j<k && a[j]<=p[i] && i*a[j]<=n)
p[i*a[j]]=a[j];
}
cout << k;
Сам алгоритм не такой шустрый как др. но создает ценный массив p[].
С ним, например, можно не только проверять простоту, но и факторизировать за O от ответа
void fact(int n){
while(n>1){
cout<<p[n]<<' ';
n/=p[n];
}
}
В смысле шустрый ? Он ведь ты написал за O(N) работает и памяти O(N) .
Если не за линейно,то есть и другие решётки Эратосфена за линейно ):D
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;
}
У меня баальшие сомнения, что он правда работает за линейное время.
Стопроцентно правильный алгоритм можно прочитать здесь. Интересно только, кто его первооткрыватель. Я тоже порыл в Интернете, и тоже не нашёл именно этого алгоритма. Есть очень близкие по идее алгоритмы, но такой поразительной простоты ни у одного из линейных решёт нет. Неужто открытие Лопатина?..
GeorgeeChebanov, по-видимому надо просто во внутреннем цикле условие "j<k" исправить на "j<k && t<=p[i ]".
Определение проблемы
Для начала, вспомним, что существует так называемоерешето Эратосфена, позволяющее решать нашу задачу за 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]],
то каждое из них в цикле во внутреннем цикле будет пройдено ровно один раз. Также ровно один раз в перед внутренним циклом будет обработано каждое простое число. Таким образом, каждое из чисел обрабатывается ровно один раз и, следовательно, получаем линейный алгоритм
GeorgeeChebanov, по-видимому надо просто во внутреннем цикле условие "j<k" исправить на "j<k && t<=p[i ]".
Да, конечно.
Что читали на сборах я не знаю.
Мне это примерно в такой реализации объясняли в Зимней компьютерной школе (параллель С+).
В смысле шустрый ? Он ведь ты написал за O(N) работает и памяти O(N) .
Если не за линейно,то есть и другие решётки Эратосфена за линейно ):D
по скорости исполнения.
да асимптотика хороша, но у меня быстрее работает такой код
int n = (int)1e7;
vector <bool> prime(n+1,true);//bool в 8 раз меньше памяти -> влезает в кеш(иногда)
v[0]=v[1]=0;
for(int i=2;i*i<=n;i++)
if(prime[i])
for(int j=i+i;j<=n;j+=i)
prime[j]=0;
Ыыыы
Он не может работать быстрее логически. Подумай разумно. Там линейно, тут больше гораздо.
Тогда нужно писать вот так,вместо +, использовать умножить,и это ускорит во много раз твою программу.
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;
Ыыыы
Он не может работать быстрее логически. Подумай разумно. Там линейно, тут больше гораздо.
Согласен.
Я имел ввиду то что у линейного больше константа.
при n = 1e6 обыгрывает в ~1.5 раза(надо проверить)
А... Тогда понятно Зачем тогда Линейный алгоритм
Я не пробовал,надо будет проверить
Сейчас проверю и скажу мой отчёт
Буду проверять на Delphi, там точное время узнаю.
Проверять буду для 4e7 = 40 000 000 .
И так на 4e7, получилось что оба алгоритма работают приблизительно одинаково около 1,7 секунд.
Из этого вывод что линейный алгоритм хуже,так как он требует массив длинной N типа (INT), тогда как второй алгоритм требует массив длиной N, но типа (BOOL), что сокращает количество памяти в четыре раза.
vectror<bool> сокращает память не в 4, а в 32 раза, потому что внутренне он реализован так, чтобы хранить информацию в битах, а не байтах.
Не знаю, но я не поэтому сравнивал
Тип BOOL идёт домножение на 1
Тип INT идёт домножение на 4
Следовательно в 4 раза .
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Решето Эратосфена