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

Быстрая проверка натурального числа на простоту - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Фоновая коррекция изображения http://www.cyberforum.ru/cpp-beginners/thread660353.html
Мне надо написать прогу, которая корректировала бы фон изображения по алгоритму:Для каждого пикселя изображения 3 (результат) : (R3,G3,B3)=(R2-R1,G2-G1,B2-B1)+Del, где Del это значение scrollbar от -255 до 255, R1,G1,B1 - значения пикселей фона, R2,G2,B2 - значение пикселей изображения, которое надо изменить. Вот код: void __fastcall TForm1::ScrollBar1Change(TObject *Sender) { int...
C++ выполните расчет стоимости, использованного интернет-трафика помогите пожалуйста, написать программу в visual c++: Выполните расчет стоимости, использованного интернет-трафика, если в ночные часы предоставляется скидка в 20%. (стоимость мегабайта и время начала скачивания вводятся пользователем, тариф определяется по времени начала). Добавлено через 1 час 16 минут как я поняла, мне нужно ввести с клавиатуры стоимость мегабайта и время суток. если это... http://www.cyberforum.ru/cpp-beginners/thread660348.html
Элементарный математический код, но почему то всегда равно 0,0000 C++
Элементарный математический код, но почему то всегда равно 0,0000. Тут я еще использую старые функции ввода-вывода, потому что так надо на лабораторную. Вот код: #include<iostream> #include<stdio.h> #include<conio.h> #include<math.h> using namespace std; int main() {
Нахождение суммы ряда с заданной точностью C++
Помогите решить задачу что то не как не могу определить с чего начать.
C++ Количество точек с целочисленными координатами внутри (не включая границ) произвольного многоугольника http://www.cyberforum.ru/cpp-beginners/thread660306.html
Есть вот такая задача. Координаты вершин подаются в порядке обхода по часовой стрелке, многоугольник может быть и невыпуклым. Решение будет основываться на исп. формулы Пика, однако есть 2 проблемы: 1) Как найти площадь такого многоугольника по координатам вершин (прошу растолковать формулу или поделиться ссылкой на источник). 2) Определение кол - ва целочисленных точек на сторонах. Спасибо.
C++ Ошибка 2094 Задали написать класс, вот собственно он: #pragma hdrstop #pragma argsused #include <iostream.h> #include <tchar.h> #include <stdio.h> class Array { int *a; int n; подробнее

Показать сообщение отдельно
Thinker
Эксперт C++
4219 / 2193 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
31.10.2012, 12:03  [ТС]     Быстрая проверка натурального числа на простоту
можно использовать двоичный поиск. сложность алгоритма
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// n - количество бит в числе a
int Search(unsigned long long a, int n)
{
   int i = 0;
   while (n)
   {
       n >>= 1;
       if (a >> n)
       {
           i += n;
           a >>= n;
       }
   }
   return i;
}
в среднем будет O(ln n). А сложность алгоритма
C++
1
2
3
4
5
6
7
int Search(unsigned long long a)
{
   int i;
   for(i = -1; a; a >>= 1, i++)
      ;
   return i;
}
в среднем будет O(n). Поэтому первый алгоритм в среднем работает в разы быстрее второго.

Первый алгоритм максимум сделает 6 проверок, второй - 64 проверки. почувствуйте разницу.

Добавлено через 14 минут
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых.
Я Вам про этот модуль m и писал в предыдущих постах. Увеличивал я именного его. Это и есть период. Странно, а я думал, что Вы понимали меня))
 
Текущее время: 14:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru