Форум программистов, компьютерный форум 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
02.05.2013, 18:50     Эффективный алгоритм поиска простых чисел на С++
Ternsip, скриншоты и коды подсчёта операций прилагаю, если что то захочешь обсудить по +1 на операцию не вопрос.

Вобщем так у меня вышло почти в 3 раза эффективней (55 к операций против 190 к у тебя), причём я думаю тут не арифметическая а геометрическая зависимость в числе операций. О понятности кода моего и твоего говорить тоже не буду. Остаётся добавить что в нолике твой алгоритм вылетает.

Мой код из поста 19
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
#include <cmath>
#include <iostream>
using namespace std;
 
bool isSimple(int num);
double OPCount = 0;
 
int main()
{
    int nCount  = 0;
    for(int num = 0; num <= 3571; num++)
    {
        if(isSimple(num))
            cout<<(nCount++)<<" - "<<num<<endl;
//      else
//          continue;
//      if( nCount && nCount % 80 == 0 )
//          system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0;
}
 
bool isSimple(int num)
{
    int i;
    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;
    }
    for(i = 9 + 2; i <= num / 10 && bSimple; i += 2)
    {
        OPCount += 1;
        if( i != num )
            bSimple = num % i != 0;
    }
    return bSimple;
}
Твой код из поста 26 (я взял последний т.к ты указал что он самый последний и доработанный)
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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
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 += 1;
        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(2, 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()
{
    int nCount  = 0;
    for(int num = 1; num <= 3571; num++)
    {
        if(test(num))
            cout<<(nCount++)<<" - "<<num<<endl;
     //   else
       //     continue;
      //  if( nCount && nCount % 80 == 0 )
        //    system("pause");
    }
    cout<<"Total count of operations : "<<OPCount<<endl;
    system("pause");
    return 0; 
}
Миниатюры
Эффективный алгоритм поиска простых чисел на С++   Эффективный алгоритм поиска простых чисел на С++  
 
Текущее время: 12:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru