Форум программистов, компьютерный форум 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
04.05.2013, 00:29     Эффективный алгоритм поиска простых чисел на С++
ЗЫ: Хотя решил для себя проверить код Ternsip, для этого соорудил сэйв результатов от 1Е6 до 1Е7 и разобрал моим алгоритмом (скрин и алгоритмы прилагаю)
Генератор чисел на базе кода 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
108
109
110
111
#include <iostream>
#include <fstream>
#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);
    ofstream ofs("1E61E7.txt");
    long long nCount  = 0;
    for(long long num = 1E6; num < 1E7; num++)
    {
        if(test(num))
        {
            nCount++;
            cout<<"\rNUM  : "<<num;
            cout<<" ITERS : "<<OPCount
                <<" COUNT : "<<nCount;
            if( ofs.is_open() )
                ofs<<num<<endl;
        }
    }
    time(&end);
    ofs.close();
    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; 
}

Код проверки значений
Кликните здесь для просмотра всего текста
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
#include <cmath>
#include <fstream>
#include <iostream>
using namespace std;
 
bool isSimple(long num);
 
int main()
{
    long num;
    long nCount  = 0;
    ifstream ifs("1E61E7.txt");
    if(!ifs.is_open())
        cout<<"ERROR OPEN 1E61E7.txt"<<endl;
    else
    while(!ifs.eof())
    {
        if(ifs>>num)
        if(isSimple(num))
        {
            nCount++;
            cout<<"\rNUM : "<<num<<" IS SIMPLE ";
        }
        else
            cout<<"\rNUM : "<<num<<" NOT SIMPLE "<<endl;
    }
    system("pause");
    return 0;
}
 
bool isSimple(long num)
{
    long i     = 0;
    long limit = 10;
    bool bSimple = true;
    if( num < 0 )
        num *= -1;
    for(i = 2; i <= 9 && bSimple; i++)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"\t\t\tDIVISOR : "<<i;
        
    }
    if( bSimple )
    while(limit * limit < num)
    {
          limit   *= 10;
    }
    for(i = 9 + 2; i <= limit && bSimple; i += 2)
    {
        if( i != num )
            bSimple = num % i != 0;
        if(!bSimple)
            cout<<"\t\tDIVISOR : "<<i;
    } 
    return bSimple;
}

Как видим даже с увеличенной точностью
Цитата Сообщение от Ternsip Посмотреть сообщение
-=ЮрА=-, Вот последняя версия, чтобы вопросов не возникало на счёт правильности
вопросы всё же возникают, около 68 штук
Список вопросов
Кликните здесь для просмотра всего текста
NUM : 1010651 NOT SIMPLE DIVISOR : 821
NUM : 1032533 NOT SIMPLE DIVISOR : 587
NUM : 1056331 NOT SIMPLE DIVISOR : 727
NUM : 1090987 NOT SIMPLE DIVISOR : 853
NUM : 1122337 NOT SIMPLE DIVISOR : 241
NUM : 1314631 NOT SIMPLE DIVISOR : 811
NUM : 1314721 NOT SIMPLE DIVISOR : 37
NUM : 1333603 NOT SIMPLE DIVISOR : 1033
NUM : 1373653 NOT SIMPLE DIVISOR : 829
NUM : 1440217 NOT SIMPLE DIVISOR : 73
NUM : 1491511 NOT SIMPLE DIVISOR : 7
NUM : 1493857 NOT SIMPLE DIVISOR : 547
NUM : 1537381 NOT SIMPLE DIVISOR : 877
NUM : 1539287 NOT SIMPLE DIVISOR : 227
NUM : 1566589 NOT SIMPLE DIVISOR : 229
NUM : 1638501 NOT SIMPLE DIVISOR : 3
NUM : 1645393 NOT SIMPLE DIVISOR : 113
NUM : 1746553 NOT SIMPLE DIVISOR : 367
NUM : 1748921 NOT SIMPLE DIVISOR : 691
NUM : 1803601 NOT SIMPLE DIVISOR : 601
NUM : 1805131 NOT SIMPLE DIVISOR : 271
NUM : 1809457 NOT SIMPLE DIVISOR : 13
NUM : 1815049 NOT SIMPLE DIVISOR : 487
NUM : 1880082 NOT SIMPLE DIVISOR : 2
NUM : 1904033 NOT SIMPLE DIVISOR : 797
NUM : 1968557 NOT SIMPLE DIVISOR : 1087
NUM : 1975231 NOT SIMPLE DIVISOR : 103
NUM : 2030341 NOT SIMPLE DIVISOR : 823
NUM : 2255843 NOT SIMPLE DIVISOR : 823
NUM : 2281049 NOT SIMPLE DIVISOR : 617
NUM : 2310829 NOT SIMPLE DIVISOR : 79
NUM : 2337301 NOT SIMPLE DIVISOR : 883
NUM : 2593909 NOT SIMPLE DIVISOR : 73
NUM : 2604331 NOT SIMPLE DIVISOR : 571
NUM : 2671601 NOT SIMPLE DIVISOR : 17
NUM : 2687089 NOT SIMPLE DIVISOR : 577
NUM : 2913181 NOT SIMPLE DIVISOR : 1151
NUM : 2926381 NOT SIMPLE DIVISOR : 647
NUM : 2955451 NOT SIMPLE DIVISOR : 367
NUM : 2995147 NOT SIMPLE DIVISOR : 463
NUM : 3052063 NOT SIMPLE DIVISOR : 7
NUM : 3125281 NOT SIMPLE DIVISOR : 1021
NUM : 3139319 NOT SIMPLE DIVISOR : 283
NUM : 3231229 NOT SIMPLE DIVISOR : 617
NUM : 3342827 NOT SIMPLE DIVISOR : 1493
NUM : 3366631 NOT SIMPLE DIVISOR : 31
NUM : 3488347 NOT SIMPLE DIVISOR : 733
NUM : 3523801 NOT SIMPLE DIVISOR : 31
NUM : 3597889 NOT SIMPLE DIVISOR : 241
NUM : 3604201 NOT SIMPLE DIVISOR : 1201
NUM : 3632593 NOT SIMPLE DIVISOR : 241
NUM : 3647621 NOT SIMPLE DIVISOR : 1103
NUM : 3736011 NOT SIMPLE DIVISOR : 3
NUM : 3808603 NOT SIMPLE DIVISOR : 127
NUM : 3815011 NOT SIMPLE DIVISOR : 691
NUM : 3873097 NOT SIMPLE DIVISOR : 109
NUM : 3913003 NOT SIMPLE DIVISOR : 1399
NUM : 3942271 NOT SIMPLE DIVISOR : 811
NUM : 3985921 NOT SIMPLE DIVISOR : 1153
NUM : 4095961 NOT SIMPLE DIVISOR : 929
NUM : 4150387 NOT SIMPLE DIVISOR : 1019
NUM : 4224533 NOT SIMPLE DIVISOR : 1187
NUM : 4384693 NOT SIMPLE DIVISOR : 1873
NUM : 4453721 NOT SIMPLE DIVISOR : 461
NUM : 4592407 NOT SIMPLE DIVISOR : 157
NUM : 4698913 NOT SIMPLE DIVISOR : 1009
NUM : 4797703 NOT SIMPLE DIVISOR : 59
NUM : 4808557 NOT SIMPLE DIVISOR : 13
NUM : 4931941 NOT SIMPLE DIVISOR : 7
NUM : 5029711 NOT SIMPLE DIVISOR : 71
NUM : 5262355 NOT SIMPLE DIVISOR : 5
NUM : 5292631 NOT SIMPLE DIVISOR : 1627
NUM : 5481451 NOT SIMPLE DIVISOR : 31
NUM : 5575501 NOT SIMPLE DIVISOR : 1181
NUM : 5646989 NOT SIMPLE DIVISOR : 293
NUM : 5902849 NOT SIMPLE DIVISOR : 733
NUM : 5903497 NOT SIMPLE DIVISOR : 1087
NUM : 5979247 NOT SIMPLE DIVISOR : 1223
NUM : 5982949 NOT SIMPLE DIVISOR : 7
NUM : 6431473 NOT SIMPLE DIVISOR : 181
NUM : 6542761 NOT SIMPLE DIVISOR : 421
NUM : 6577121 NOT SIMPLE DIVISOR : 1481
NUM : 6594901 NOT SIMPLE DIVISOR : 1483
NUM : 6637546 NOT SIMPLE DIVISOR : 2
NUM : 6746749 NOT SIMPLE DIVISOR : 467
NUM : 6765826 NOT SIMPLE DIVISOR : 2
NUM : 6986827 NOT SIMPLE DIVISOR : 67
NUM : 7120513 NOT SIMPLE DIVISOR : 1009
NUM : 7126129 NOT SIMPLE DIVISOR : 241
NUM : 7344947 NOT SIMPLE DIVISOR : 2213
NUM : 7455709 NOT SIMPLE DIVISOR : 73
NUM : 7480549 NOT SIMPLE DIVISOR : 37
NUM : 7526513 NOT SIMPLE DIVISOR : 1181
NUM : 7648033 NOT SIMPLE DIVISOR : 1597
NUM : 7686647 NOT SIMPLE DIVISOR : 2531
NUM : 7788943 NOT SIMPLE DIVISOR : 883
NUM : 7828201 NOT SIMPLE DIVISOR : 37
NUM : 7859707 NOT SIMPLE DIVISOR : 887
NUM : 7879681 NOT SIMPLE DIVISOR : 1621
NUM : 7971451 NOT SIMPLE DIVISOR : 457
NUM : 8428645 NOT SIMPLE DIVISOR : 5
NUM : 8614033 NOT SIMPLE DIVISOR : 577
NUM : 8697121 NOT SIMPLE DIVISOR : 577
NUM : 8899661 NOT SIMPLE DIVISOR : 2311
NUM : 8936722 NOT SIMPLE DIVISOR : 2
NUM : 9080191 NOT SIMPLE DIVISOR : 2131
NUM : 9206623 NOT SIMPLE DIVISOR : 307
NUM : 9345541 NOT SIMPLE DIVISOR : 59
NUM : 9439201 NOT SIMPLE DIVISOR : 61
NUM : 9483706 NOT SIMPLE DIVISOR : 2
NUM : 9487153 NOT SIMPLE DIVISOR : 13
NUM : 9493903 NOT SIMPLE DIVISOR : 2179
NUM : 9504191 NOT SIMPLE DIVISOR : 1259
NUM : 9591661 NOT SIMPLE DIVISOR : 1171
NUM : 9707377 NOT SIMPLE DIVISOR : 1039
NUM : 9745291 NOT SIMPLE DIVISOR : 1669
NUM : 9964753 NOT SIMPLE DIVISOR : 337
NUM : 9999991 IS SIMPLE Для продолжения нажмите любую клавишу . . .
Миниатюры
Эффективный алгоритм поиска простых чисел на С++  
Вложения
Тип файла: rar 1E61E7.rar (1.70 Мб, 3 просмотров)
 
Текущее время: 06:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru