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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> : http://www.cyberforum.ru/cpp-beginners/thread853990.html
помогите пожалуйста решить задачку на рекурсию Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом («T» — True, «F» — False): <выражение> ...
C++ Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла Дан символ 'C' (прописная латинская буква) и текстовый файл. Создать строковый файл, содержащий все слова из исходного файла, начинающиеся этой буквой (как прописной, так и строчной). Знаки... http://www.cyberforum.ru/cpp-beginners/thread853979.html
C++ Условие в условии
Здравствуйте всем. Периодически нужно менять условия и поэтому одно из двух условий делал неактивным помещая в /*----*/ if( условие 1 /*условие 2*/ ){очень много строк}
C++ Перегруженный оператор вывода
Пытаюсь написать шаблон для работы с бинарными деревьями поиска. Возникла проблема - с ходу не соображу что к чему. при попытке распечатать дерево выдает ошибку " error LNK2019: ссылка на...
C++ Программа для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы http://www.cyberforum.ru/cpp-beginners/thread853948.html
Напишите программу для нахождения в каждой строке матрицы G(n, m) максимальный и минимальный элементы и помещения их на место первого и последнего элемента строки соответственно. Вывести на экран...
C++ Составить программу, которая по номеру детали выводит на экран её название. Вот задание. Имеется пронумерованный список деталей: 1) шуруп, 2) гайка, 3) винт, 4) гвоздь,5)болт. Составить программу, которая по номеру детали выводит на экран её название. Вот какой код я смог... подробнее

Показать сообщение отдельно
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.05.2013, 18:05
-=ЮрА=-, вот
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 <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
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);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
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;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries){
    for(int it = 0; it < tries; it++){
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
bool simple (long long a){
    int j;
    for(j = 2; j * j <= a && a % j; ++j);
    return (j * j > a && a - 1);
}
 
bool test(long long c){
    if (c < 99990001)
        return simple(c);
    return MillerRabin(c, 19);
}
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    long long n;
    cin >> n;
    for (int i = 0; i < 1000; i++) {
        if (test(n))
            puts("ok");
    }
    return 0; 
}
Добавлено через 5 минут
-=ЮрА=-, вот немного доработал
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 <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
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);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
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;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries){
    for(int it = 0; it < tries; it++){
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
bool simple (long long a){
    if (a < 2)
        return false;
    if (a == 2)
        return true;
    int j;
    for(j = 3; j * j <= a && a % j; j+=2);
    return (j * j > a && a - 1);
}
 
bool test(long long c){
    if (c <= 999900010)
        return simple(c);
    return MillerRabin(c, 19);
}
 
int main(){
    long long n;
    cin >> n;
    if (test(n))
       puts("ok");
    return 0; 
}
Добавлено через 4 минуты
-=ЮрА=-, вот ещё доработал
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
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
 
using namespace std;
 
// big numbers
 
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);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
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;
        long long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long long n, long long tries) {
    for(int it = 0; it < tries; it++) {
        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--) {
        if(b < (1 << i)) continue;
        int x = d;
        d = (long long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long long(d) * a) % n;
    }
    return (d != 1);
}
 
bool MillerRabinLow(int n) {
      if(n == 2) return true;
    if(witnessLow(2, n)) return false;
    return true;
}
 
bool test(long long c){
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main(){
    long long n;
    cin >> n;
    if (test(n))
            puts("ok");
    return 0; 
}
Добавлено через 1 минуту
-=ЮрА=-, если придумаете алгоритм много быстрее, то может удостоитесь награды и похвалы выше чем сам http://ru.wikipedia.org/wiki/%D0%9C%...B0%D1%80%D0%B8

Добавлено через 3 минуты
-=ЮрА=-, и, естественно, что решетом Эратосфена, блочным и другими нельзя пользоваться, это читы
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru