5

Дано задание: В интервале [a,b] выведите все числа, такие, что сумма их делителей, включая единицу, и не включая само число будет равна самому числу. Или -1, если таковых чисел в интервале нет.

Необходимо оптимизировать алгоритм поиска, таким образом чтобы программа не зависала при работе с большими числами. Попросту, чтобы после 80 000 не сообщала Time limit exceeded Killed. Многие типы переменных и алгоритмы я ещё не использовал, поэтому информация по данной тематике также важна.

#include <stdio.h>

int main(){
    int a, b;
    scanf("%d %d", &a, &b);

    int counter = 0;
    for(int i = a; i <= b; i++) {
        int sum = 0;
        for(int j = 1; j < i; j++) {            
            if(i % j == 0) {
                sum += j;                
            }
        }
        if(sum == i) {
           printf("%d ", i);
           counter++;
        }        
    }

    if(counter == 0) {
        printf("-1");
    }

    return 0;
}
4
  • Проще взять готовую табличку (она небольшая), чем считать... Второй вариант - считайте числа Мерсенна.
    – Harry
    14 янв 2019 в 17:55
  • @Harry, да ладно? Кстати, а при чём тут числе Мерсена? Они же простые вроде?
    – Qwertiy
    14 янв 2019 в 18:00
  • Именно :) За...колупаетесь разложения считать. А насчет чисел Мерсенна... Так ведь пока что все найденные совершенные числа из чисел Мерсенна получаются.
    – Harry
    14 янв 2019 в 18:02
  • Давайте продолжим обсуждение в чате.
    – Qwertiy
    14 янв 2019 в 18:04

2 ответа 2

5

Вот, если очень хочется именно считать... пользуясь тем, что все известные на сегодня совершенные числа четные, а еще Эйлер доказал их связь с простыми числами Мерсенна - вот мы и подбираем простые Мерсенна, которые обеспечивают совершенные числа в нужном диапазоне:

Disclaimer: код as is, сваяно на коленке, просто показать, как должно работать. Со всеми тонкостями типоразмеров и прочими просьба справляться самостоятельно и меня не трогать :)

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int isOddPrime(unsigned int u)
{
    for(unsigned int i = 3; i*i <= u; i+=2)
        if (u%i == 0) return 0;
    return 1;
}

unsigned int Perfect(unsigned int p)
{
    unsigned int Mersenne = (1u << p) - 1;
    if (!isOddPrime(Mersenne)) return 0;
    return Mersenne*(1u << (p-1));
}

int main()
{
    unsigned int a, b;
    scanf("%u %u",&a,&b);
    for(unsigned int p = 2;;++p)
    {
        unsigned long long s = (1ull << (2*p-1)) - (1ull << (p-1));
        if (s > b) break;
        if (s < a) continue;
        unsigned int res = Perfect(p);
        if (res) printf("%lu\n",res);
    }
}

Вывод к нужному виду (ну, там, -1 если чисел нет и т.п.) приведите сами...

P.S. А вообще, самая правильная программа на эту тему -

#include <stdlib.h>
#include <stdio.h>

unsigned long long perfs[] =
{
    6,28,496,8128,33550336,8589869056,
    137438691328,2305843008139952128
};

int main()
{
    unsigned long long a, b;
    scanf("%llu %llu",&a,&b);
    int was = 0;
    for(int i = 0; i < 8; ++i)
    {
        if (perfs[i] >= a && perfs[i] <= b)
        {
            was = 1;
            printf("%llu\n",perfs[i]);
        }
    }
    if (!was) puts("-1");
}

:)

P.P.S. Всю необходимую информацию было очень легко получить, погулявшись, например, в Википедию.

7
  • 1. unsigned long -> unsigned long long, а то не у всех линукс. 2. (2 << p) - 1 - должно быть 2ULL. 3. В проверку на простоту у чётных чисел должно быть return u==2;
    – Qwertiy
    14 янв 2019 в 18:22
  • @Qwertiy 1. Должно хватить unsigned long - один раз встречается unsigned long long исключительно чтоб избежать переполнения для больших чисел. 2. Согласен, исправил. 3. Блин, оно вообще не нужно, мой прокол - там же только нечетные... Оно просто не работает :)
    – Harry
    14 янв 2019 в 18:26
  • 1. unsigned long - это 32 бита на винде, но 64 на линуксе. Смысл использовать такой сомнительный тип? 3. Ну просто чтоб функция проверки была универсальная.
    – Qwertiy
    14 янв 2019 в 18:29
  • @Qwertiy Меняем на unsigned int. Я набрасывал "на коленке", спешил, просто идею показать...
    – Harry
    14 янв 2019 в 18:43
  • @Harry 2ul это что с такое, с такой записью я ещё не сталкивался 14 янв 2019 в 18:46
3

Используй алгоритм, основанный на том же подходе, что и решето Эратосфена. Сделай массив с суммой делителей, отличных от самого числа, а потом посчитай количество подходящих чисел.

var a = Array(1000000+1).fill(0)

for (var q=1; q<a.length; ++q)
  for (var w=q+q; w<a.length; w+=q)
    a[w] += q

var l=1, r=1000000, res=0

for (var x=l; x<=r; ++x)
  if (a[x] === x)
    console.log(x)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.