Как напечатать 10 идеальных чисел с заданного пользователем числа в C?

Question

Я не могу понять, как напечатать следующие десять Совершенные числа . Вот что я получил до сих пор:

#include <stdio.h>

int main() {
    int n, c = 1, d = 2, sum = 1;
    printf("Enter any number \n");
    scanf("%d", &n);
    printf("The perfect numbers are:");
    while(c <= 10) { 
        sum = 1;
        d = 2;
        while(d <= n / 2) { //perfect no
            if(n % d == 0) {
                sum = sum + d;
            }
            d++;
        }
        if(sum == n) {
            printf("%d\n", n);
        }
        c++;
    }
    return 0;
}

Вывод, который я сейчас получаю:

input: 2 (say)  
output: 6  

Что я хочу:

input: 2  
output:
6  
28  
496  
8128  
33550336  
858986905  
137438691328  
2305843008139952128  
2658455991569831744654692615953842176
191561942608236107294793378084303638130997321548169216

Я только что началкодирование. Любая помощь будет оценена.

Answer 1

Проблема целочисленного переполнения, упомянутая несколькими людьми, является существенной, но вторичной . Даже если мы исправим вашу неработающую логику и настроим ее для обработки больших целых чисел фиксированного размера:

#include <stdio.h>

int main() {
    unsigned long long number;
    printf("Enter any number \n");
    scanf("%llu", &number);
    printf("The perfect numbers are:\n");

    int total = 0;

    while (total < 10) { 
        unsigned long long sum = 1, divisor = 2;

        while (divisor <= number / 2) {
            if (number % divisor == 0) {
                sum += divisor;
            }
            divisor++;
        }

        if (sum == number) {
            printf("%llu\n", number);
            total++;
        }

        number += 1;
    }

    return 0;
}

Вы все равно не сможете пройти первые четыре совершенных числа за любое разумное время:

> ./a.out
Enter any number 
2
The perfect numbers are:
6
28
496
8128

Основная проблема заключается в том, что вы используете неверный алгоритм . Прочитайте о простых числах Мерсенна и их связи с совершенными числами, а также о тесте Лукаса-Лемера . Этот подход требует больше размышлений, но, что удивительно, не намного больше кода. И даст больше результатов быстрее (хотя, в конечном счете, также увязнет).

Answer 2

Вы должны поставить счетчик после того, как найдете идеальное число, поэтому увеличение c должно произойти в операторе if, который проверяет идеальное число, например:

if(sum==n){
    printf("%d",n);
    c++;
}

После этого вынужно увеличить число, называемое n, примерно так:

n++;

и, основываясь на числах, @Jonathan Leffler прав, вы должны использовать правильные переменные.

Answer 3

Исследования , разделяй и властвуй

Совершенные числа имеют вид 2 ^{p - 1} * (2 ^p - 1).

Коду потребуется расширенная точность для формирования 191561942608236107294793378084303638130997321548169216

Повышение эффективности

Итерация до <= n / 2 требует слишком многодолго. Итерация до <= n / d

// while(d <= n / 2) {
while(d <= n / d) {

Пример улучшенного кода:

bool isprime(unsigned long long x) {
  if (x > 3) {
    if (x % 2 == 0) {
      return false;
    }
    for (unsigned long t = 3; t <= x / t; t += 2) {
      if (x % t == 0) {
        return false;
      }
    }
    return true;
  }
  return x >= 2;
}

Дополнительно: См. Тест простоты Лукаса – Лемера для быстрого простого теста чисел Мерсенна

---

Приведенный ниже код работает для всех, кроме 10-го совершенного числа, так как код должен проверять isprime (2 ⁶⁷ - 1), и я должен что-то оставить для OP.

static void buff_mul(char *buff, unsigned power_of_2) {
  unsigned long long m = 1ull << power_of_2;
  size_t len = strlen(buff);
  unsigned long long carry = 0;
  for (size_t i = len; i > 0;) {
    i--;
    unsigned long long sum = (buff[i] - '0') * m + carry;
    buff[i] = sum % 10 + '0';
    carry = sum / 10;
  }
  while (carry) {
    memmove(buff + 1, buff, ++len);
    buff[0] = carry % 10 + '0';
    carry /= 10;
  }
}

void print_perfext(unsigned p) {
  // 2**(p-1) * (2**p - 1)
  assert(p > 1 && p <= 164);
  char buff[200] = "1";
  buff_mul(buff, p);
  buff[strlen(buff) - 1]--; // Decrement, take advantage that the LSDigit is never 0
  buff_mul(buff, p - 1);
  puts(buff);
  fflush(stdout);
}

//unsigned next_prime(unsigned first_numeber_to_test_if_prime) {
#include <stdio.h>

int main() {
  unsigned p = 0;
  for (unsigned i = 0; i < 9; i++) {
   // If p prime && 2**p − 1 is prime, then 2**(p − 1) * (2**p − 1) is a perfect number.
    while (!isprime(p) || !isprime((1uLL << p) - 1))
      p++;
    printf("%2u ", p);
    print_perfext(p);
    p++;
  }
  return 0;
}

Выход

 2 6
 3 28
 5 496
 7 8128
13 33550336
17 8589869056
19 137438691328
31 2305843008139952128
61 2658455991569831744654692615953842176

Answer 4

Из вывода, который вы написали, я верю, что вы хотите показать 10 первых совершенных чисел. Теперь вы показываете только 6, потому что вы показываете их от 1 до 10. В этом диапазоне есть только 6. Я написал вот что:

#include <stdio.h>
int isperfect(int input) {
int sum = 0, value = input / 2;
do {
    if (input % value == 0) sum += value;
    value--;
} while (value);
if (input == sum) return 1;
else return 0;
}
int main() {
int i;
int count;
for (i = 2, count = 0; count < 4; i++) {
    if (isperfect(i) == 1) {
        count++;
        printf("%d\n", i);
    }
}
return 0;
}

Но я не рекомендую считать больше 4, потому что это займет слишком много времени