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

Быстрый поиск совершенных чисел - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ bool функция, нужен разбор http://www.cyberforum.ru/cpp-beginners/thread920795.html
bool not_url_char(char c) { static const string url_char="~,./?!@#$%^&*()_-+=;'"; return !(isalnum(c)||find(url_char.begin(), url_char.end(), c)!=url_char.end()); } Данная функция должна...
C++ Массив: Как скопировать двумерный массив в другой массив? Как скопировать двумерный массив в другой массив? http://www.cyberforum.ru/cpp-beginners/thread920785.html
Добавить в класс возможность вычисления значенний с плавающей точкой C++
Есть код программи , надо добавить в него возможность считать не только целие числа, а й реальние. Как разобрать строку ? Чтоб получились числа типа float #include <vcl> #include <conio> #include...
найти ошибку замена максимального C++
Задача: Найти и поменять местами элементы, имеющие минимальное и максимальное значения в массиве. Код: #include "stdafx.h" #include <iostream> #include <sstream> #include <string> #include...
C++ Реализация acos http://www.cyberforum.ru/cpp-beginners/thread920677.html
И ребят помогите разобраться в чем ошибки здесь, делаю лабораторную по методу секущих И еще как можно графически выполнить метод секущих через Dos Box? Заранее благодарю за помощь #include...
C++ как вызвать msvcbuild из командной строки доброе время суток пытаюсь скомпилировать luaJit. установил вижуал студио 2010. делаю все как в этой инструкции http://luajit.org/install.html. вызвал командную строку вижуал студио. зашел в... подробнее

Показать сообщение отдельно
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5

Быстрый поиск совершенных чисел - C++

10.07.2013, 12:27. Просмотров 4585. Ответов 1
Метки (Все метки)

Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую тему.
Напомню, что
Совершенное число — натуральное число, равное сумме всех своих собственных делителей (т. е. всех положительных делителей, отличных от самого́ числа).
Доказано, что все четные совершенные числа имеют вид http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{p-1}(2^p-1), где p и http://www.cyberforum.ru/cgi-bin/latex.cgi?2^p-1 простые. Нечётных совершенных чисел до сих пор не обнаружено, однако не доказано и то, что их не существует.
Предлагаю быстрый алгоритм нахождения совершенных чисел до числа http://www.cyberforum.ru/cgi-bin/latex.cgi?5\cdot 10^{18}. По желанию значение N можно менять.
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
#include <iostream>
#include<cstdlib>
const unsigned long long N = 5000000000000000000llu;
 
// решето Эратосфена
void Eratosfen(char *a, unsigned long n)
{
    unsigned long i, j;
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i*i <= n)
    {
        for(j = i << 1; j < n; j += i)
            a[j] = 0;
        i += 2;
        while (i < n && a[i] == 0)
            i += 2;
    }
}
 
// количество значащих бит числа
unsigned long Count(unsigned long long a)
{
   unsigned long long count;
   for(count = 0; a; a >>= 1)
      ++count;
   return count;        
}
 
// проверка на простоту
int Prime(unsigned long long a)
{
   unsigned long long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}
 
int main()
{
   char *eratosfen;
   unsigned long long sov, i, n = (Count(N) >> 1) + 1; 
   eratosfen = (char *)calloc(n, sizeof(*eratosfen));
   Eratosfen(eratosfen, n);
   // вывод совешенных чисел
   for(i = 2; i < n; ++i)
      if (eratosfen[i] && Prime((1 << i) - 1))
      {
         sov = ((1llu << i) - 1llu) << (i - 1llu);
         std::cout << (unsigned long long)sov << std::endl;
      }
   
   free(eratosfen);
   return 0;    
}
8
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru