// G. Hagopian -- PPP4 ex 11

/*
11. Create a program to find all the prime numbers between 1 and 100.
One way to do this is to write a function that will check if a number is
prime (i.e., see if the number can be divided by a prime number smaller
than itself) using a vector of primes in order (so that if the vector is
called primes, primes[0]==2, primes[1]==3, primes[2]==5, etc.). Then write
a loop that goes from 1 to 100, checks each number to see if it is a prime,
and stores each prime found in a vector. Write another loop that lists the
primes you found. You might check your result by comparing your vector of
prime numbers with primes. Consider 2 the first prime.
*/
#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int x, vector<int> primes) {
	for (int i = 0; primes[i] <= sqrt(x); ++i)
		if (x % primes[i] == 0) return false;
	return true;
}

int main() {
	vector<int> primes{ 2 };
	unsigned max{};
	cout << "What is the max for our list of primes? ";
	cin >> max;
	for (int i = 3; i < max; ++i) {
		if (isPrime(i, primes)) primes.push_back(i);
	}
	for (int p : primes) cout << p << " ";
}