Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Динамические структуры данных. Составить программу, которая содержит текущую информацию о книгах в библиотеке https://www.cyberforum.ru/ cpp-beginners/ thread847093.html
не могу решить Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: • номер УДК; • фамилию и инициалы автора; • название; • год издания;...
Функции библиотеки для работы со строками и символами C++
С помощью текстового редактора создать файл, содержащий текст, длина которого не превышает 700 символов (длина строки текста не должна превышать 70 символов). Имя файла должно иметь расширение...
C++ Функции библиотеки для работы со строками и символами
Помогите с решением С помощью текстового редактора создать файл, содержащий текст, длина которого пе превышает 1000 символов (длина строки текста не должна превышать 70 символов). Имя файла...
C++ Структуры: хранение данных о планшетных сканерах Помогите, не могу решить Для хранения данных о планшетных сканерах описать структуру вида: struct scan_info{ char model; // наименование модели int price: // цена double x_s1ze: //... https://www.cyberforum.ru/ cpp-beginners/ thread847085.html
C++ Не пойму тайный смысл фразы Страуструпа https://www.cyberforum.ru/ cpp-beginners/ thread847064.html
Читаю Страуструпа про компоновку и нашел там такое предложение: Причина, по которой в заголовочные файлы рекомендуется включать определения простых констант, а определения агрегатов включать не...
C++ Дан текстовый файл. Переписать компоненты файла в другой файл, заменив при этом каждое сочетание букв “no” на “on”
Дан текстовый файл. Переписать компоненты файла в другой файл, заменив при этом каждое сочетание букв “no” на “on”. :( Помогите, пожалуйста!!
C++ сортировка методом Шелла
не работает сортировка методом Шелла. выдает только 3 числа массива, а четвертый повторяет. не могу понять в чем причина. #include<iostream.h> #include<math.h> #include<fstream.h> void main() {...
C++ Рассчитать значения у для значений х, равных 4, 5, ., 28, если у задается следующей формулой: у = 2t2 + 5,5t – 2, t = х + 2 # include <iostream.h> # include <math.h> # include <windows.h> int main() { int x,y; for (int x=4; x <=29; x++) https://www.cyberforum.ru/ cpp-beginners/ thread847004.html
C++ Бинарное дерево для анализа текста https://www.cyberforum.ru/ cpp-beginners/ thread847001.html
Здравствуйте! Помогите решить проблему. нет перехода между char и int. struct tnode { char*word; int count; struct tnode*left; struct tnode*right; };
C++ Список. Двоичное число в виде списка. Определите функцию, которая прибавляет к данному числу единицу напишите программу, которая представляет двоичное число в виде списка. Определите функцию, которая прибавляет к данному числу единицу. заранее спасибо за помощь. https://www.cyberforum.ru/ cpp-beginners/ thread846978.html
667 / 195 / 29
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 22:14  [ТС] 0

Простые числа. Список простых чисел

29.04.2013, 22:14. Просмотров 4197. Ответов 16
Метки (Все метки)

Ответ

Немного улучшил тест Миллера, т.к. в нём было переполнение 64 - битного типа. теперь всё ок
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
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;
}


Вернуться к обсуждению:
Простые числа. Список простых чисел
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.04.2013, 22:14
Готовые ответы и решения:

Найти все двухзначные простые числа, определив функцию для вычисления простых чисел
Найти все двухзначные простые числа, определив функцию для вычисления простых чисел на C++

Удалить все простые числа и найти среднее арифметическое до и после удаления простых чисел
Помогите пожалуйста разобрать ошибки и дописать программу. Ошибки: Функции должны возвращать...

Создать односвязный список из последовательности чисел, удалить из него все простые числа
Прошу помощи, не могу понять в чем ошибка, надо создать односвязный список из последовательности...

Найти простые числа, которые можно разбить еще на два простых числа
Найти на промежутке количество простых чисел, которые можно разбить еще на два простых числа. К...

16
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.