Форум программистов, компьютерный форум 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...
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++ Упрощение логического выражения Всем привет. Сейчас решаю задачу про шахматного коня по книжке Дейтелов. Там предлагается высчитать доступность каждой клетки и двигать коня туда, где доступность наименьшая. Чтобы ее рассчитать,... подробнее

Показать сообщение отдельно
castaway
Эксперт С++
4885 / 3020 / 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)
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru