Форум программистов, компьютерный форум 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 - двумерный массив,... подробнее

Показать сообщение отдельно
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
21.07.2013, 18:13
Нашел на StackOverflow и внес незначительные изменения. ( http://stackoverflow.com/questions/4...umber-is-prime )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <chrono>
 
using namespace std;
 
__int64 power( int a, int n, int mod )
{
    __int64 power = a, result = 1;
    while ( n ) {
        if ( n & 1 ) result = (result * power) % mod;
        power = (power * power) % mod;
        n >>= 1;
    }
    return result;
}
 
bool witness( int a, int n )
{
    int t,u,i;
    __int64 prev,curr;
 
    u = n >> 1;
    t = 1;
 
    while ( !(u & 1) ) {
        u >>= 1;
        ++t;
    }
 
    prev = power( a, u, n );
    for ( i = 1; i <= t; ++i ) {
        curr = (prev * prev) % n;
        if ( (curr == 1) && (prev != 1) && (prev != n - 1) ) return true;
        prev = curr;
    }
    if ( curr != 1 ) return true;
    return false;
}
 
inline bool IsPrime( int number )
{
    if ( ((!(number & 1)) && number != 2) || (number < 2) || (number % 3 == 0 && number != 3) ) return false;
 
    if ( number < 1373653 ) {
        for( int k = 1; 36 * k * k - 12 * k < number; ++k )
            if ( (number % (6 * k + 1) == 0) || (number % (6 * k - 1) == 0) )
                return false;
        return true;
    }
 
    if ( number < 9080191 ) {
        if ( witness( 31, number ) ) return false;
        if ( witness( 73, number ) ) return false;
        return true;
    }
 
    if ( witness(  2, number ) ) return false;
    if ( witness(  7, number ) ) return false;
    if ( witness( 61, number ) ) return false;
    return true;
}
 
int main()
{
    chrono::system_clock::time_point a = chrono::system_clock::now();
    for ( unsigned int i = 0; i < 1000000; i++ ) {
        if ( IsPrime( i ) ) {
            cout << i << endl;
        }
    }
    chrono::system_clock::time_point b = chrono::system_clock::now();
    cout << chrono::duration_cast< chrono::milliseconds >( b - a ).count() << " ms.\n";
    return 0;
}
Среди чисел от 0 до 1 000 000 находит простые ~ за 386 ms. Ноутбук с Core i3, MinGW 4.7.3 (32 бита), ключ оптимизации -O0 (т.е. отключена)

Добавлено через 7 минут
Без вывода ~ 132 ms. (уже на MinGW 4.8.1)
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru