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

Поиск простых чисел - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Почему не хочет читать статические члены-данние класса???? http://www.cyberforum.ru/cpp-beginners/thread359305.html
Вот мой код.Вибивает ерор:1>SAS.obj : error LNK2001: неразрешенный внешний символ ""private: static int Distance::m_kilk" (?m_kilk@Distance@@0HA)".В чем дело????? #include "stdafx.h"...
C++ контейнер map Помогите, пожалуйста дописать программу. Определите карту, в которой ключом является фамилия семьи, а значением вектор, который содержит имя ребёнка и его возраст. Заполните карту по крайней мере 6... http://www.cyberforum.ru/cpp-beginners/thread359291.html
функция по массиву с выбором C++
Во всех приведенных ниже вариантах использовать меню для организации работы программы, исходные данные предварительно записать в текстовый файл. Разработать схему алгоритма и программу, используя...
C++ Ошибка С2143.
День добрый. Вылезла такая проблема. При компиляции студия пишет: Ошибка 1 error C2143: синтаксическая ошибка: отсутствие ";" перед "->" d:\test refuel\Form1.h 547 1 Test refuel Вот код модуля:...
C++ Найти наибольший общий делитель трех чисел http://www.cyberforum.ru/cpp-beginners/thread359281.html
заданы 3 числа найти их наибольший общий делитель
C++ Найти наименьшее общее кратное трех чисел заданы 3 числа найти их наименьшее общее кратное Теги выделения кода предназначены для выделения кода, а не задания. Если Вам необходимо решения именно на C++, укажите это в названии темы или в... подробнее

Показать сообщение отдельно
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
02.10.2011, 23:42
На основе Миллера-Рабина:

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
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
 
typedef unsigned long long ull_t;
 
static const int small_primes[] =
{
      2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,  61,
     67,  71,  73,  79,  83,  89,  97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251
};
static const size_t small_primes_size = sizeof(small_primes) / sizeof(*small_primes);
 
size_t binary_length(ull_t num)
{
    size_t len = 1;
 
    num >>= 1;
 
    while ((num >>= 1) != 0)
        ++len;
 
    return len;
}
 
ull_t fast_pow(ull_t a, ull_t x, ull_t P)
{
    ull_t y = 1;
    ull_t a_mod_P = a % P;
    ull_t shift_x = 1;
 
    for (size_t i = 0; shift_x != 0; ++i)
    {
        shift_x = x >> i;
 
        if ((shift_x & 1) == 1)
            y = (y * a_mod_P) % P;
 
        a_mod_P = (a_mod_P * a_mod_P) % P;
    }
 
    return y % P;
}
 
bool prime_test(ull_t p)
{
    if (p == 1)
        return false;
 
    for (size_t i = 0; i < small_primes_size && p != small_primes[i]; ++i)
        if (p % small_primes[i] == 0)
            return false;
 
    size_t r = binary_length(p);
    ull_t t = p - 1;
    size_t s = 0;
 
    while (t % 2 == 0)
    {
        t /= 2;
        ++s;
    }
 
    for (size_t i = 0; i < r; ++i)
    {
        ull_t a = static_cast< ull_t >(2 + ((p - 2) - 2) * rand() / RAND_MAX);
        ull_t x = fast_pow(a, t, p);
        bool key = false;
 
        if (x != 1 && x != p - 1)
        {
            for (size_t j = 0; j < s - 1; ++j)
            {
                x = x * x % p;
 
                if (x == 1)
                    return false;
 
                if (x == p - 1)
                    key = true;
            }
 
            if (key == false)
                return false;
        }
    }
 
    return true;
}
 
int main()
{
    std::ifstream fin("INPUT.TXT");
 
    ull_t number;
 
    fin >> number;
 
    std::ofstream fout("OUTPUT.TXT");
 
    fout << (prime_test(number) ? "YES" : "NO");
 
    return 0;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru