Project Euler # 23, не могу найти проблему в программе

Ссылка на сайт : http://projecteuler.net/problem=23

Совершенное число — это число, для которого сумма его собственных делителей
точно равен числу. Например, сумма правильных
делителями 28 будет 1 + 2 + 4 + 7 + 14 = 28, что означает, что 28
это идеальное число.

Число n называется дефицитным, если сумма его собственных делителей равна
меньше чем n и называется обильным, если эта сумма превышает n.

Поскольку 12 — это наименьшее численное число, 1 + 2 + 3 + 4 + 6 = 16,
наименьшее число, которое можно записать как сумму двух чисел
24. Математическим анализом можно показать, что все целые числа
больше, чем 28123, может быть записано как сумма двух обильных чисел.
Тем не менее, этот верхний предел не может быть уменьшен в дальнейшем путем анализа
хотя известно, что наибольшее число, которое не может быть
выражается как сумма двух чисел меньше, чем этот предел.

Найдите сумму всех натуральных чисел, которые нельзя записать в виде
сумма двух обильных чисел.


Ответ на проблему 4179871, моя программа показывает 3797954.

Прежде всего, я делаю функцию для заполнения массива abundant [] всеми обильными числами ниже 28124. Это прекрасно работает, потому что я гуглил обильные числа, и они точно совпадают с моим массивом.

Во-вторых, у меня есть другой массив со всеми числами 1-28123, я предполагаю, что ВСЕ из них «не могут быть записаны как сумма двух чисел с избытком». Все это записано в массив hold [].

Наконец, я избавляюсь от чисел, которые МОГУТ быть записаны как сумма двух чисел с избытком, добавляя все числа в избытке [] со всеми числами в избытке [], и устанавливая это значение hold [] в 0. (hold [ обильный [от 0 до n] + обильный [от 0 до n]] = 0)
Добавить все оставшиеся номера в удержании [], я только получаю 3797954

Я знаю, что эта программа не очень эффективна, так как она добавляет все обильные числа ко всем обильным числам, но она должна работать просто отлично. Что с этим не так?


#include <iostream>
#include <cmath>

using namespace std;

int hold[28124];
int abundant[7000]; //hold abundant numbers, there are only 6919 abundant numbers below 28123

bool abundance(int x){  //returns true if x is abundant
int counter = 1;    //holds "proper divisors" of numbers, default by 1 because every int is divisible by 1
for (int i = 2; i < sqrt(x); i++){   //finds all divisors 2 - sqrt(n)
if (x % i == 0){
counter += i;
counter += x / i;
}
}
int y = sqrt(x);
if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
counter += sqrt(x);
}
if (counter > x){
return true;
} else {
return false;
}
}

int main()
{
int counter = 0;
for (int i = 0; i < 28124; i++){ //assumes every number cannot be written as the sum of two abundant numbers,
hold[i] = i;                 //goes up to 28123 because "it can be shown that all integers greater
}                                //than 28123 can be written as the sum of two abundant numbers." - project euler
for (int j = 10; j < 28124; j++){
if (abundance(j) == true){  //copies all abundant numbers up to 28123 to abundant[]
abundant[counter] = j;
counter++;
}
}

for (int m = 0; m < counter; m++){  //adds all numbers in abundant[], with all numbers in abundant[]
for (int n = 0; n < counter; n++){
if (abundant[m]+abundant[n] < 28124){
hold[abundant[m]+abundant[n]] = 0; //sum of the abundant numbers in hold[] is set to 0
} //hold[] now holds all numbers that cannot be written as the sum of 2 abundant numbers
}
}
int counter2 = 0;
for (int x = 0; x < 28124; x++){
counter2 += hold[x];
}
cout << counter2 << endl;

}

5

Решение

Проблема в вашем abundance функция, а именно эта часть:

int y = sqrt(x);
if (x % y == 0){   //adds sqrt(n) if its modulus to n is 0
counter += sqrt(x);
}

x % (int)sqrt(x) == 0 не означает, что sqrt(x) является целым числом Простой контрпример — 2. sqrt(2) около 1.414, или просто 1 как целое число Но 2 % 1 == 0даже если это не квадратный корень.

Чтобы исправить свой код, измените эту часть на:

int y = sqrt(x);
if (y * y == x){   //adds sqrt(n) if sqrt(n) is an integer
counter += y;
}

И вы получите правильные результаты.

7

Другие решения

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

1

my_set = set([i for i in range(1, 28123)])
print ('original sum',sum(my_set))
my_list = list(my_set)
my_l1 =[]
for k in range(12, int(my_list[-1]/2+1)):
a = 0
for j in range(1, int(k/2+1)):
if k%j == 0:
a += j

if a > k:
my_l1.append(k)
my_set.remove(k*2)
#Calculating the sum of all the numbers which can be written as the sum of two abundant numbers
l = 0
my_l2 = set([])
for d in my_l1:
l += 1
k = l
while k < len(my_l1):
a_s = d + my_l1[k]
my_l2.add(a_s)
k += 1
my_set.difference_update(my_l2)
print ('sum of all abbundant numbers:',sum(my_set))

вот мой код для задачи 23 Project Euler, что с этим не так? Пока я не беспокоюсь о времени выполнения, я просто хочу правильный ответ.

0
По вопросам рекламы [email protected]