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

Поиск совершенного числа N через цикл for - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.97
aptik
1 / 1 / 0
Регистрация: 06.04.2009
Сообщений: 6
14.05.2009, 21:23     Поиск совершенного числа N через цикл for #1
Сложить программу с помощью цикла for

Задание
Дано некоторое число N. Сложить программу поиска “совершенных” чисел меньших за N. “Совершенным” есть число, которое равно суме своих делителей, за исключением самого себя.

Помогите пожалуйста. Очень срочно надо. Заранее благодарен.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrAndrey_ka
 Аватар для MrAndrey_ka
77 / 77 / 2
Регистрация: 13.05.2009
Сообщений: 536
Записей в блоге: 1
14.05.2009, 21:38     Поиск совершенного числа N через цикл for #2
хоть формулу дай по какой проверить "совершенное число"
Rififi
 Аватар для Rififi
2330 / 1045 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
14.05.2009, 21:40     Поиск совершенного числа N через цикл for #3
aptik,
с++ совершенное число
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
15.05.2009, 01:24     Поиск совершенного числа N через цикл for #4
Вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "stdafx.h"
#include <iostream>
using namespace std;
 
int main(int argc,char* argv[])
{
    setlocale(0,"");
    int i,n,j,
        c;
    cout << "Введите n: ";
    wcin >> n;
    _flushall();
    for(i = 1;i < n;i++){
        c = 0;
        for(j = 1;j < n;j++)
            if((i%j == 0) && (j != i))
                c = c + j;
        if(i == c)
            cout << i << " совершенное число." << endl;
    }
    getchar();
    return 0;
}
MrAndrey_ka
 Аватар для MrAndrey_ka
77 / 77 / 2
Регистрация: 13.05.2009
Сообщений: 536
Записей в блоге: 1
15.05.2009, 10:50     Поиск совершенного числа N через цикл for #5
insolent, введи число около 10 000 и уснешь перед монитором.Rififi, дал правильную ссылку(я имею ввиду первую в списке) , я вчера 2 часа разные варианты решения перебирал, но быстрее чем по ссылке не работал не один!
grrrrr
 Аватар для grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
15.05.2009, 13:20     Поиск совершенного числа N через цикл for #6
Цитата Сообщение от Rififi Посмотреть сообщение
Второй раз натыкаюсь на эту ссылку и второй раз улыбаюсь Классно придумано!

Добавлено через 29 минут 45 секунд
Rififi, а как можно свой запрос вставить?
MrAndrey_ka
 Аватар для MrAndrey_ka
77 / 77 / 2
Регистрация: 13.05.2009
Сообщений: 536
Записей в блоге: 1
15.05.2009, 14:16     Поиск совершенного числа N через цикл for #7
Цитата Сообщение от grrrrr Посмотреть сообщение
Rififi, а как можно свой запрос вставить?
Это ты о чем?
Rififi
 Аватар для Rififi
2330 / 1045 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
15.05.2009, 14:24     Поиск совершенного числа N через цикл for #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
grrrrr,
Rififi, а как можно свой запрос вставить?
заходишь на http://ru.lmgtfy.com/ пишешь свой поиск, он тебе конструирует ссылку

Добавлено через 5 минут 40 секунд
вот еще, но это для тяжелых случаев :loL:
c++ совершенное число
grrrrr
 Аватар для grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
15.05.2009, 16:11     Поиск совершенного числа N через цикл for #9
Rififi, Спасибо!
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
15.05.2009, 19:55     Поиск совершенного числа N через цикл for #10
Цитата Сообщение от MrAndrey_ka Посмотреть сообщение
insolent, введи число около 10 000 и уснешь перед монитором.Rififi, дал правильную ссылку(я имею ввиду первую в списке) , я вчера 2 часа разные варианты решения перебирал, но быстрее чем по ссылке не работал не один!
Ничего подобного. Вводил я 10 000 и программа с успехом находила 4 совершенных числа. А время затратила - пару сек
Русдеч
Сообщений: n/a
18.01.2011, 21:31     Поиск совершенного числа N через цикл for #11
Цитата Сообщение от insolent Посмотреть сообщение
Ничего подобного. Вводил я 10 000 и программа с успехом находила 4 совершенных числа. А время затратила - пару сек
Да, безусловно, числа 6, 28, 496, 8128 оно находит в первые секунды запука программы, но вот пятое число, равное 33 550 336. Компьютер еще до него не добрался, хотя выполняется программа около 10 с половиной часов. Мне интересно, за какое кол-во времени комп найдёт пятое число. Кто нибудь пробовал?

Добавлено через 9 часов 20 минут
Цитата Сообщение от Русдеч Посмотреть сообщение
Да, безусловно, числа 6, 28, 496, 8128 оно находит в первые секунды запука программы, но вот пятое число, равное 33 550 336. Компьютер еще до него не добрался, хотя выполняется программа около 10 с половиной часов. Мне интересно, за какое кол-во времени комп найдёт пятое число. Кто нибудь пробовал?
Скажу сразу, по алгоритму, предложенному пользователем insolent, программа будет искать 5, 6, 7 числа очень долго. Я искал по подобному алгоритму. Но, послу многих часов работы программы, она так и не подобралась к 5-му совершенному.
Ниже представлена программа, которая ищет совершенные числа гораздо быстрее - 0m31.203s потраченного времени на поиск 7-ми совершенных против многочасового поиска 5-го (которого он так и не нашёл - мне надоело ждать).
Из википедии: "Алгоритм построения чётных совершенных чисел описан в IX книге Начал Евклида, где было доказано, что число 2^{p-1}(2^p-1) является совершенным, если число 2^p-1 является простым" Отсюда и плясал
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
#include <math.h>
#include <stdio.h>
long sov(long);
long sov(long x)
{
   long i, j, sum;
   short int k;
   //Цикл нахождения ПРОСТОГО числа
   for (i = 2; i <= x; i++)
   {
      sum = 0;
      for (j = 1; j <= sqrt(i); j++)
         if ((i%j == 0) && (i%i == 0))
            sum += 1;
    //Если ПРОСТОЕ число найдено...
      if (sum == 1)
      {
      /*...сравним его с числами 2^k - 1. Если числа равны, умножим число на i.
      Результатом будет совершенное число*/
         for (k = 2; k <= 128; k++)
            if (i == (pow(2, k) - 1))
               printf("Простое: %ld\tСовершенное:%.0f\n", i, i*(pow(2, k-1)));
       }
    }
}
 
main(void)
{
   sov(524287);
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.01.2011, 22:11     Поиск совершенного числа N через цикл for #12
Русдеч, Если заинтересует, я когда-то решал такую задачу:
Совершенные числа
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.
Входные данные

Входной файл INPUT.TXT содержит числа M и N, разделенные пробелом. (1 <= M <= N <= 5*10^18)
Выходные данные

В выходной файл OUTPUT.TXT выведите по одному числу в строке в порядке возрастания все совершенные числа, находящихся на отрезке [M, N]. В том случае, когда таких чисел нет следует вывести «Absent».
Вот код:
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
#include "stdafx.h"
#include <stdio.h>
#include <math.h>
 
int main()
{
    int mas[8]={2, 3, 5, 7, 13, 17, 19, 31};
    long M, N, temp;
    int fl=1, i, fl1=0;
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    scanf("%ld%ld", &M, &N);
    for(i=0; i<8 && fl; i++)
    {
        temp=long(pow((double)2,(double) mas[i]-1)*(pow((double)2,(double)mas[i])-1));
        if(temp>=M && temp<=N)
        {
            printf("%ld\n", temp);
            fl1=1;
        }
        if(temp>N)
            fl=0;
    }
    if(!fl1){printf("Absent");}
  return 0;
}
Запустите, введите 0 и 5000000000000000000 (5*10^18). Выведет все совершенные числа в этом диапазоне менее чем 1 секунда.
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
22.05.2012, 10:19     Поиск совершенного числа N через цикл for #13
Найти все совершенные числа в заданном интервале.
Мой вариант, но где-то с ошибкой . Помогите найти.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
 int i, j, gr, sum; // Переменные
 
   printf ("Vvedite verhnuu granicu intervala:"); // Введите верхнюю границу инттервала
   scanf ("%d", &gr); // Запомнить ввод
  
  for (i>=1; i<gr; i++) // Совершенное число является натуральныи, 
                         // счетчик устанавливаем от 1 до верхней границы   
   {         
    sum=0; 
    for (j>=1; j<gr; j++ );
     {
      if ((i%j==0) && (j!=i));
       { sum=sum+j; }
     if (sum==i)     
      { printf ("Sovershenniy chisla: %d", i); }   
     }
   }      
 getch(); // Ожидать нажатия любой клавиши
 return 0; // Вернуть 0 функции int main()
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.05.2012, 10:29     Поиск совершенного числа N через цикл for #14
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 int main()
{
 int i, j, gr, sum; // Переменные
 
   printf ("Vvedite verhnuu granicu intervala:"); // Введите верхнюю границу инттервала
   scanf ("%d", &gr); // Запомнить ввод
  
  for (i=1; i<=gr; i++) // Совершенное число является натуральныи, 
                         // счетчик устанавливаем от 1 до верхней границы   
   {         
    sum=0; 
    for (j=1; j<i; j++ )
     {
      if (i%j==0)
       sum=sum+j; 
    }
     if (sum==i)     
      { printf ("Sovershennoe chislo: %d\n", i); }   
     
   }      
 getch(); // Ожидать нажатия любой клавиши
 return 0; // Вернуть 0 функции int main()
}
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
22.05.2012, 11:20     Поиск совершенного числа N через цикл for #15
valeriikozlov, Почему сократили проверку if ((i%j==0) || (j!=i)) ; ? Ведь делитель совершенного числа не должен быть равен самому совершенному числу.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
22.05.2012, 11:27     Поиск совершенного числа N через цикл for #16
Потому что в коде у вас j < i
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
22.05.2012, 12:47     Поиск совершенного числа N через цикл for #17
valeriikozlov, Про верхней границе 100000 (сто тысяч) твоя программа находит 4 числа и зависает. При 99999 нет.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.05.2012, 13:39     Поиск совершенного числа N через цикл for #18
Цитата Сообщение от Shman Посмотреть сообщение
valeriikozlov, Про верхней границе 100000 (сто тысяч) твоя программа находит 4 числа и зависает. При 99999 нет.
Это не моя программа, а Ваша (мной подправленная до рабочего состояния).
Число 8128, порграмма находит примерно за 2-3 секунды.
И при 99999 и при 100000 работает очень долго (я не дождался результата).
А вот для быстрого поиска совершенных чисел из диапазона от 0 до 5000000000000000000 (5*10^18) можете воспользоваться кодом, который описан в посте № 12 этой темы.
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
22.05.2012, 15:37     Поиск совершенного числа N через цикл for #19
Еще меня интересует что елают циклы. Я понимаю так:
C++
1
2
3
4
5
6
7
8
9
10
11
  for (i=1; i<=gr; i++) // Совершенное число является натуральныи, 
                         // счетчик устанавливаем от 1 до верхней границы   
   {         
    sum=0; // Обнуляем сумму
  for (j=1; j<i; j++) // Стечик делителей
     {
      if (i%j==0) // Если остаток деления числа на делитель равен 0, то...
       {sum=sum+j;} // к sum=0 прибавляется последний возможный делитель 
    }
     if (sum==i) // Если сумма равна числу из интервала, то..
     { printf ("\n %d.", i); }  // напечатать это число
Добавлено через 1 час 8 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Это не моя программа, а Ваша (мной подправленная до рабочего состояния).
Число 8128, порграмма находит примерно за 2-3 секунды.
А при вводе 100000 думает 2 минуты и не находит ни одно числа.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2015, 20:49     Поиск совершенного числа N через цикл for
Еще ссылки по теме:

Поиск совершенного числа в массиве C++
C++ Вложенный цикл и списки. Поиск одинаковых
Поиск числа в двумерном массиве (бинарный поиск) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
EPOLO
0 / 0 / 1
Регистрация: 15.12.2015
Сообщений: 3
16.12.2015, 20:49     Поиск совершенного числа N через цикл for #20
лови программку)На самом деле очень все легко.Только сделал чуть по другому. Вводишь число и программа проверяет совершенное или нет.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
void main()
{
    int n,i,sum=1;
    printf("введите число:");
    scanf("%d",&n);
    for(i=2;i<=n/2;i++)
    {
        if(!(n%i))
            sum+=i;
    }
    if(sum==n)
        printf("число совершенное");
    else 
        printf("нет");
}
Yandex
Объявления
16.12.2015, 20:49     Поиск совершенного числа N через цикл for
Ответ Создать тему
Опции темы

Текущее время: 04:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru