prime_numbers.cpp File Reference

Get list of prime numbers. More...

#include <iostream>
#include <vector>

Include dependency graph for prime_numbers.cpp:

Functions
std::vector< int >	primes (size_t max)
int	main ()

Detailed Description

Get list of prime numbers.

See also

primes_up_to_billion.cpp sieve_of_eratosthenes.cpp

Function Documentation

main()

int main

(

void

)

main function

           {
    std::cout << "Calculate primes up to:\n>> ";
    int n = 0;
    std::cin >> n;
    std::vector<int> ans = primes(n);
    for (int p : ans) std::cout << p << ' ';
    std::cout << std::endl;
}

Here is the call graph for this function:

primes()

std::vector< int > primes

(

size_t

max

)

Generate an increasingly large number of primes and store in a list

                                  {
    std::vector<int> res;
    std::vector<bool> is_not_prime(max + 1, false);
    for (size_t i = 2; i <= max; i++) {
        if (!is_not_prime[i]) {
            res.emplace_back(i);
        }
        for (int p : res) {
            size_t k = i * p;
            if (k > max) {
                break;
            }
            is_not_prime[k] = true;
            if (i % p == 0) {
                break;
            }
        }
    }
    return res;
}

Here is the call graph for this function: