Projekt Euler nr 23, nie może znaleźć problem w programie

Question

Link: http://projecteuler.net/problem=23

Doskonałym liczba jest liczbą, dla której suma jej właściwych dzielników jest dokładnie równa liczbie. Na przykład suma odpowiednich dzielników 28 wynosi 1 + 2 + 4 + 7 + 14 = 28, co oznacza, że ​​28 jest liczbą doskonałą.

Liczba n jest nazywana niedostateczną, jeśli suma jej właściwych dzielników jest równa mniejsza niż n i nazywa się ją obfitą, jeśli suma ta przekracza n.

Jako 12 jest najmniejsza liczba obfity, 1 + 2 + 3 + 4 + 6 = 16, to najmniejszą liczbę, która może być zapisana jako sumy dwóch liczb jest bogate 24. Za pomocą analizy matematycznej, może być pokazane, że wszystkie liczby całkowite większe niż 28123 mogą być zapisane jako suma dwóch obfitych liczb. Jednak ten górny limit nie może być dalej obniżany przez analizę , chociaż wiadomo, że największa liczba, która nie może być wyrażona jako suma dwóch obfitych liczb, jest mniejsza niż ten limit.

Znajdź sumę wszystkich dodatnich liczb całkowitych, które nie mogą być zapisane jako suma dwóch obfitych liczb.

---

Odpowiedzią na problem jest 4.179.871, mój program pokazuje 3797954.

Przede wszystkim robię funkcją wypełnić tablicę obfite [] ze wszystkimi obfitych liczbach poniżej 28124. To działa doskonale w porządku, ponieważ szukałem wielu liczb i pasowały do ​​mojej tablicy.

Po drugie, mam kolejną tablicę z numerami 1-28123, zakładam, że WSZYSTKIE z nich "nie mogą być zapisane jako suma dwóch obfitych liczb". Wszystkie są zapisane w tablicy hold [].

W końcu, pozbywam się liczb, które MOGĄ być zapisane jako suma dwóch obfitych liczb, przez dodanie wszystkich liczb w obfitych [] ze wszystkimi liczbami w dużej ilości [] i ustawienie tej wartości hold [] na 0 (przytrzymaj [obfite [0 do n] + obfite [0 do n]] = 0) Dodaj wszystkie pozostałe numery w luku [], dostaję tylko 3797954

Wiem, że ten program nie jest bardzo wydajny, ponieważ dodaje wszystkie obfite liczby do wszystkich obfitych liczb, ale powinno działać dobrze. Co jest z tym nie tak?

---

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

} 

Answer 1

Problem jest w swojej funkcji abundance, szczególnie ta część:

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 nie oznacza, że ​​sqrt(x) jest liczbą całkowitą. Prosty kontrprzykład to 2. sqrt(2) jest około 1.414 lub tylko 1 jako liczba całkowita.Ale 2 % 1 == 0, nawet jeśli nie jest to pierwiastek kwadratowy.

Tak, aby naprawić swój kod, aby zmienić tę część:

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

I dostaniesz poprawnych wyników.

Answer 2

Można spojrzeć na kod pokazany here - choćby dlatego, że dostaje właściwą odpowiedź. Bez skopiowania tego, co zostało tam zrobione, możesz na przykład potwierdzić, czy problem występuje w generatorze liczb obfitych lub w drugiej części. To może pomóc ci dowiedzieć się, gdzie idziesz źle.

Answer 3

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)) 

Oto mój kod dla problemu23 Projekt Euler, co jest nie tak z tym? Na razie nie interesuje mnie środowisko uruchomieniowe, chcę tylko poprawnej odpowiedzi.

pyton