Project Euler 7 - про простые числа :)
Запись от Тамика размещена 05.07.2019 в 15:09
Показов 2214
Комментарии 4
Метки c++
|
Новый Эйлер готов! |
Метки c++
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 4
Комментарии
-
Проверка на 0 не лишняя только там, где запись в память дороже чтения и проверки значения.
Если же стоимость записи меньше или равна стоимости чтения плюс сравнения с 0, то можно смело писать 0 поверх 0 ;-)
C++ 1 2 3 4 5 6 7 8 9
void fill_sieve() { sieve.resize(n); std::iota(sieve.begin(), sieve.end(), 0); for (int i=2; i*i<n; ++i) for (int j=i*i; j<n; ++j) sieve[j]=0; sieve.erase(std::remove(sieve.begin(), sieve.end(), 0), sieve.end()); }
Запись от bormant размещена 09.07.2019 в 15:35 
-
Мне кажется, в Вашем примере выйдет слишком много ненужной работы - каждый раз проходить по вектору, размер которого миллион. Стоит ли оно того? И у Вас опечатка, наверное, ибо идти нужно не по каждому элементу, а j += i.
Сообщение от bormant
Запись от Тамика размещена 11.07.2019 в 13:30
-
1) Да, опечатка.
2) Откуда ненужная работа?
C++ 1 2 3 4 5 6 7 8 9
void fill_sieve() { sieve.resize(n); std::iota(sieve.begin(), sieve.end(), 0); for (int i=2; i*i<n; ++i) for (int j=i*i; j<n; j+=i) sieve[j]=0; sieve.erase(std::remove(sieve.begin(), sieve.end(), 0), sieve.end()); }
Если ненужной работы хотелось избежать (и проверка sieve[i]==0 не опечатка), то было бы:C++ 1 2 3 4 5 6 7 8 9 10 11 12 13
void fill_sieve() { sieve.resize(n); std::iota(sieve.begin(), sieve.end(), 0); for (int i=2; i*i<n; ++i) for (int j=i*i; j<n; j+=i) { if (sieve[i]==0) continue; sieve[j]=0; } sieve.erase(std::remove(sieve.begin(), sieve.end(), 0), sieve.end()); }
ведь i во внутреннем цикле не меняется... Или я опять что-то проглядел (в первый раз почудилось в условии (sieve[j]==0), отсюда был и соответствующий комментарий)?C++ 1 2 3 4 5 6 7 8 9 10
void fill_sieve() { sieve.resize(n); std::iota(sieve.begin(), sieve.end(), 0); for (int i=2; i*i<n; ++i) if (sieve[i]!=0) for (int j=i*i; j<n; j+=i) sieve[j]=0; sieve.erase(std::remove(sieve.begin(), sieve.end(), 0), sieve.end()); }
Запись от bormant размещена 12.07.2019 в 22:44
-
Да, в плане выноса проверки на ноль за пределы второго фора - полностью согласна
Сообщение от bormant
Запись от Тамика размещена 17.07.2019 в 10:36
Сообщение от bormant
