Finding Prime Numbers (division and Sieve of Eratosthenes)

FindingPrimeNumbers.cpp

// https://www.youtube.com/watch?v=eKp56OLhoQs&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25&index=5&t=0s

#include <iostream>
#include <list>
#include <cmath>

// Trial Division = O(sqrt(n))
bool isPrime(int n) {
    bool result = true;
    // Use square root optimization
    for (int i = 2; i <= sqrt(n); i++) {
        int remain = n % i;
        if (remain == 0) {
            result = false;
            break;
        }
    }
    return result;
}

// O(n)
std::list<int> findByTrial(int n) {
    std::list<int> primes;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            primes.push_back(i);
        }
    }
    return primes;
};

// Sieve of Eratosthenes
std::list<int> sieveErastosthenes(int n) {
    int primes[n + 1];
    // Every number is prime
    // Big O (n)
    for (int i = 0; i < n + 1; i++) {
        primes[i] = 1;
    }
    // Discard 0 and 1
    primes[0] = 0;
    primes[1] = 0;

    // Discard every multple of every prime
    // HERE CAN BE AN OPTIMIZATION!!!!!!!!!
    // Big O (n * loglog n)
    for (int i = 2; i <= sqrt(n); i++) {
        if (primes[i] == 1) {
            for (int j = 2; j * i <= n; j++) {
                primes[j * i] = 0;
            }
        }
    }
    // Translate all this to list instead of the PAIN arrays!
    std::list<int> result;
    for (int i = 2; i < sizeof(primes)/sizeof(int); i++) {
        if (primes[i] == 1) {
            result.push_back(i);
        }
    }
    return result;
};

// Helper function
void printNumbers(std::list<int> list) {
    for (int n : list) {
        std::cout << n << ", ";
    }
    std::cout << "" << std::endl;
}

int main() {
    int n;
    std::cout << "Números primeros del 2 al ?:" << std::endl;
    std::cin >> n;
    std::list<int> primes = findByTrial(n);
    // CASE 1 = Big O(n * sqrt(n)):
    std::cout << "Números primos Big O(n * sqrt(n)):" << std::endl;
    printNumbers(primes);
    std::cout << "" << std::endl;
    // CASE 2 = Big O(n * sqrt(n)):
    std::cout << "Números primos Big O(n * sqrt(n)):" << std::endl;
    primes = sieveErastosthenes(n);
    printNumbers(primes);
    return 0;
}