如何用C打印用户给定数字的10个完美数字

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("%dn", 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("%llun", number);
total++;
}
number += 1;
}
return 0;
}

在任何合理的时间内，你仍然无法通过前四个完美数字：

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

主要问题是您使用了错误的算法。阅读梅森素数，以及它们与完美数的关系，以及Lucas Lehmer检验。这种方法需要更多的思考，但令人惊讶的是，没有更多的代码。并且会更快地产生更多的结果(尽管最终也会陷入困境。(

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;
}

高级：关于梅森数的快速素数测试，请参见Lucas–Lehmer素性测试

---

下面的代码适用于除第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("%dn", i);
}
}
return 0;
}

但我不建议计数超过4，因为需要太多时间