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

Определить, является ли заданное натуральное число совершенным - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ разложение тангенса http://www.cyberforum.ru/cpp-beginners/thread307395.html
Бодрого утра....вот не могу справиться с ошибками...буду очень благодарна, кто поможет... #include <iostream> #include <conio.h> #include <math.h> using namespace std; #define PI...
C++ Преобразовать строку, заменив точками все двоеточия, встречающиеся среди первых n/2 символов, и заменив точками все восклицательные знаки... 14.24. Дана строка. Преобразовать ее, заменив точками все двоеточия, встречающиеся среди первых n/2 символов, и заменив точками все восклицательные знаки, встречающиеся среди символов, стоящих после... http://www.cyberforum.ru/cpp-beginners/thread307390.html
работа с двумерным массивом. C++
Доброго всем времени суток, помогите решить задачку(знаю что элементарная но что то не выходит ни чего) Дана целочисленная прямоугольная матрица. Определить количество столбцов, ни содержащих ни...
Вывести на экран часть массива расположенную выше главной диагонали. C++
Дан двумерный массив размером 10х10. Вывести на экран часть массива расположенную выше главной диагонали. Нужно решить через СИ
C++ Простейший графисеский редактор http://www.cyberforum.ru/cpp-beginners/thread307381.html
Реализовать простейший векторный графический редактор со следующим набором функциональных возможностей: задание цвета фона, на котором происходит рисование. рисование точек различного цвета и...
C++ Разработайте алгоритм и напишите программу с использованием вложенных операторов цикла for для расчета СУММА(от i=1 до n)СУММА(от j=1 до m)(2*i+j) Вот исходник // программа на использование оператора цикла for #include <iostream.h> void main() { int y,n,m; y = 0; for (n=1; n<2; n=+2) { for (m=1;m<3;m=+n) подробнее

Показать сообщение отдельно
azusdex
0 / 0 / 0
Регистрация: 20.07.2011
Сообщений: 6
20.07.2011, 01:51
Всего известных совершенных чисел на апрель 2010 года было 47. Но я думаю столько не нужно.
Самый известный способ это или простые числа Мерсенна(был приведен выше, так что описывать нет смысла) или алгоритм Евклида (тоже основан на простых числах): 2^(p-1) * 2^p-1 так что бы 2^p-1 являлось простым числом, например p=2 => (2^2-1) = 3 простое число, 2^(2-1)*2^2-1 = 6 совершенное число.
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
 
void perfectNumbers(unsigned long long max){
    //с помощью unsigned long long позволяет найти 137 438 691 328
    
    cout << "\nThis numbers is Perfect: " << endl;
    unsigned long long a, b;
    for (long i = 2; i < max; i++){
        a = pow(2,i)-1;
        if (isPrime(a) == 1){  //проверяем если это простое число
            b = pow(2,(i-1));
            if (a > max || a*b > max) //если да то умножаем на вторую часть 
                break;
            cout << b*a << endl;
        }
    }
}
 
 
//функция для нахождения простых чисел
bool isPrime(unsigned long long num){
    for(unsigned long long i = 2; i < (sqrt(num) + 1); i++){
        if(num % i == 0){
            return 0;
            break;
        }
    }
    return 1;
}
Алгоритм сразу откидывает все нечетные числа, так как совершенных нечетных чисел еще не найдено.
Если число p^2-1 простое (это и есть число Мерсенна) то проверки дальше не нужны, просто умножаем на вторую часть. Можно доработать функцию нахождения простых чисел, если не дорабатывать то первые пять чисел находит за секунду, шестое больше минуты, седьмое за минут 20, дальше не пробовал потому что не уверен если можно вывести такое гигантское число
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.