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

Эффективный алгоритм поиска простых чисел на С++ - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> : http://www.cyberforum.ru/cpp-beginners/thread853990.html
помогите пожалуйста решить задачку на рекурсию Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> ::= T | F | And(<выражение> , <выражение>) | Or(<в ыражение> ,<выражение>)
C++ Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла, начинающиеся этой буквой (как прописной, так и строчной). Знаки препинания, расположенные в начале и в конце слов, не учитывать. Если исходный файл не содержит подходящих слов, оставить результирующий файл пустым. Нужно СРОЧНО!!! Добавлено через 10 минут хотя бы... http://www.cyberforum.ru/cpp-beginners/thread853979.html
C++ Условие в условии
Здравствуйте всем. Периодически нужно менять условия и поэтому одно из двух условий делал неактивным помещая в /*----*/ if( условие 1 /*условие 2*/ ){очень много строк}
C++ Перегруженный оператор вывода
Пытаюсь написать шаблон для работы с бинарными деревьями поиска. Возникла проблема - с ходу не соображу что к чему. при попытке распечатать дерево выдает ошибку " error LNK2019: ссылка на неразрешенный внешний символ "class std::basic_ostream<char,struct std::char_traits<char> > & __cdecl operator<<(class std::basic_ostream<char,struct std::char_traits<char> > &,class Tree<double>)"...
C++ Программа для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы http://www.cyberforum.ru/cpp-beginners/thread853948.html
Напишите программу для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы и помещения их на место первого и последнего элемента строки соответственно. Вывести на экран исходную и полученную матрицы в общепринятом виде.
C++ Составить программу, которая по номеру детали выводит на экран её название. Вот задание. Имеется пронумерованный список деталей: 1) шуруп, 2) гайка, 3) винт, 4) гвоздь,5)болт. Составить программу, которая по номеру детали выводит на экран её название. Вот какой код я смог придумать. Но почему-то он не хочет работать. Где ошибка ? #include<iostream.h> #include<conio.h> void main () { int a; clrscr(); cout <<"a="; cin>>a; switch (a); { case1: cout<<"shyryp";... подробнее

Показать сообщение отдельно
-=ЮрА=-
Заблокирован
Автор FAQ
03.05.2013, 23:19     Эффективный алгоритм поиска простых чисел на С++
Внизу коды и сравнительная отработка, для значений до 1Е6 и до 1Е7 включительно
(больший объём проверять для меня с моим 1ядерным ПК 2,7 ГГц слишком долго),
буду благодарен за сравнительные тесты на больших порядках скажем до 1Е8-10. В своём коде изъял домножение на 3.2 судя из тестов без него - данное домножение было лишним
Мой код
Кликните здесь для просмотра всего текста
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
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
 
bool isSimple(long long num);
double OPCount = 0;
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    long long nCount  = 0;
    for(long long num = 2; num < 1E7; num++)
    {
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    time(&end);
    system("cls");
    cout<<"\rITERS : "<<OPCount
        <<" COUNT : "<<nCount;
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(long long num)
{
    long long i     = 0;
    long long limit = 10;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    OPCount += 1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
          OPCount += 1;
    }
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        OPCount += 1;
    } 
    return bSimple;
}

Код Ternsip
Кликните здесь для просмотра всего текста
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
 
// big numbers
 
double OPCount = 0;
long long mulmod(long long a, long long b, long long MOD){
    if (b == 0) return 0;
    long long res = mulmod(a, b >> 1, MOD);//+1
    res += res;//+2
    res %= MOD;//+3
    OPCount += 4;
    return (b & 1)? (a + res) % MOD : res;//+4
}
 
bool witness(long long a, long long n) {
    long long d = 1;
    long long b = n - 1;
    for(int i = 63; i >= 0; i--)
    {
        if(b < pow(2.0, i)) continue;
        OPCount += i;//как того требует pow(i)
        long long x = d;//+1
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1){ return true; OPCount += 1;}//+1
        if ((b >> i) & 1) {d = mulmod(d, a, n);OPCount += 1;}
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries) {
    for(int it = 0; it < tries; it++) 
    {
        OPCount += 2;//rand && %
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
// low numbers
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witnessLow(int a, int n) 
{
    int d = 1;
    int b = n - 1;
    for(int i = 31; i >= 0; i--)
    {
        OPCount += 1;
        if(b < (1 << i)) continue;
        int x = d;
        OPCount += 1;
        d = (long long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) {return true; OPCount += 1;}
        if((b >> i) & 1){ d = (long long(d) * a) % n; OPCount += 1;}
    }
    OPCount += 1;
    return (d != 1);
}
 
bool MillerRabinLow(int n) 
{
    OPCount += 1;
      if(n == 2) return true;
    if(witnessLow(19, n)) return false;
    return true;
}
 
bool test(long long c)
{
    OPCount += 1;
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
    time_t beg;
    time_t end;
    time(&beg);
    long long nCount  = 0;
    for(long long num = 2; num < 1E7; num++)
    {
        if(test(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
        }
    }
    time(&end);
    cout<<"\n\tSTATISTIC:"<<endl;
    cout<<"program started : "<<asctime(localtime(&beg));
    cout<<"program stopped : "<<asctime(localtime(&end));
    cout<<"work time : "<<difftime(end, beg)<<endl;
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}

В заключение ещё раз прошу либо писать по сути, либо не писать вообще, ваши предположения подкрепляйте тестами кодами, скриншотами. Остаётся добавить что судя из отработки на порядке 1Е7 мой код выдал 664579 против 664780 простых чисел у Ternsip (что может косвенно говорить о новых брежах алгоритма по типу отмеченных в посте 53. Хотелось бы узнать точное число простых чисел на промежутке 1 - 1Е7
Миниатюры
Эффективный алгоритм поиска простых чисел на С++   Эффективный алгоритм поиска простых чисел на С++   Эффективный алгоритм поиска простых чисел на С++  

Эффективный алгоритм поиска простых чисел на С++  
 
Текущее время: 01:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru