Форум программистов, компьютерный форум CyberForum.ru

Алгоритм нахождения простых чисел - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Включить в программу только одну ф-цию из библиотеки http://www.cyberforum.ru/cpp-beginners/thread926539.html
Из библиотеки boost я могу выбрать одну нужную мне ф-ию (boost/algorithm/cxx11/all_of.hpp), можно ли это сделать с std::all_of (как пример) // all_of example #include <iostream> // std::cout #include <algorithm> // std::all_of #include <array> // std::array #include <boost/algorithm/cxx11/all_of.hpp> using namespace boost::algorithm; bool isOdd ( int i ) { return i%2; }
C++ Как объявить массив объектов одного класса в другом классе, а затем поместить в него объекты? Как объявить массив объектов одного класса в другом классе, а затем поместить в него объекты? http://www.cyberforum.ru/cpp-beginners/thread926534.html
Обьясните понятие как работает Операция языка C++
Простите пожалуста, если я не видел аналогичной темы. Вот Операции сдвига ( « и » ) применяются к целочисленным операндам. Они сдвигают двоичное представление первого операнда влево или вправо на количество двоичных разрядов, заданное вторым операндом. При сдвиге влево ( « ) освободившиеся разряды обнуляются. При сдвиге вправо (>) освободившиеся биты заполняются нулями, если...
C++ Почему в switch нельзя определять переменные?
int main() { setlocale(LC_ALL, "Russian"); int n; std::cout << "Введите число: "; std::cin >> n; switch (n)
C++ Проясните освобождение памяти http://www.cyberforum.ru/cpp-beginners/thread926507.html
Допустим есть такой код: typedef struct COORDINATE { QVector<int> x; QVector<int> y; QVector<int> z; } Coordinate; public: void SaveCoord();
C++ Упрощение логического выражения Всем привет. Сейчас решаю задачу про шахматного коня по книжке Дейтелов. Там предлагается высчитать доступность каждой клетки и двигать коня туда, где доступность наименьшая. Чтобы ее рассчитать, надо, грубо говоря, из каждой клетки походить конём. Идея, как считать доступность уже есть, выглядит она примерно так (тут как минимум нет проверки границы массива): //board - двумерный массив,... подробнее

Показать сообщение отдельно
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.07.2013, 17:38     Алгоритм нахождения простых чисел
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Можно кусок кода (алгоритм)!!!
категорически от вас требуется, чтобы проверка каждого числа на простоту выполнялась за корень. это выглядит так:
C++
1
2
3
4
5
6
bool _isprime(int n) {
   for(int i=2; i*i <= n; ++i)
      if(n % i == 0)
         return false;
   return true;
}
далее вы можете применять любые эвристики. самая очевидная: проверять только нечетные делители. практически целесообразно отсекать пару частых делителей. короче говоря, можно прийти к такому:

C++
1
2
3
4
5
6
7
bool _isprime(int n) {
   if(n & 1 == 0) return false;
   for(int i=3; i*i <= n; i += 2)
      if(n % i == 0)
         return false;
   return true;
}
Добавлено через 2 минуты
асимптотически, алгоритмы совершенно одинаковы, но в среднем второй должен работать в два раза быстрее.
 
Текущее время: 10:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru