Форум программистов, компьютерный форум, киберфорум
Наши страницы
Тамика
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

Project Euler 7 - про простые числа :)

Запись от Тамика размещена 05.07.2019 в 15:09

Новый Эйлер готов!
Размещено в Без категории
Просмотров 147 Комментарии 4
Всего комментариев 4
Комментарии
  1. Старый комментарий
    Аватар для bormant
    Проверка на 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 bormant вне форума
  2. Старый комментарий
    Цитата:
    Сообщение от bormant Просмотреть комментарий
    Проверка на 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());
    }
    Мне кажется, в Вашем примере выйдет слишком много ненужной работы - каждый раз проходить по вектору, размер которого миллион. Стоит ли оно того? И у Вас опечатка, наверное, ибо идти нужно не по каждому элементу, а j += i.
    Запись от Тамика размещена 11.07.2019 в 13:30 Тамика вне форума
  3. Старый комментарий
    Аватар для bormant
    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());
    }
    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());
    }
    Если ненужной работы хотелось избежать (и проверка sieve[i]==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());
    }
    ведь i во внутреннем цикле не меняется... Или я опять что-то проглядел (в первый раз почудилось в условии (sieve[j]==0), отсюда был и соответствующий комментарий)?
    Запись от bormant размещена 12.07.2019 в 22:44 bormant вне форума
    Обновил(-а) bormant 12.07.2019 в 22:51
  4. Старый комментарий
    Цитата:
    Сообщение от bormant Просмотреть комментарий
    Если ненужной работы хотелось избежать (и проверка sieve[i]==0 не опечатка), то было бы:
    Да, в плане выноса проверки на ноль за пределы второго фора - полностью согласна
    Запись от Тамика размещена 17.07.2019 в 10:36 Тамика вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru