Algorithm for finding prime numbers

[atmetal]

I have an assignment where I'm supposed to write a function that determines all the prime numbers greater than 2 up to a user-inputted number and stores them in a vector. The assignment instructions don't do a very good job at explaining how the algorithm works. So without understanding the concept outside the code, it's hard for me to even start. The instructions say that the outer loop will iterate from 2 to n-1. I understand that part. The inner loop will iterate from 2 to floor(sqrt(n)). The instructions say that the floor() part is "the largest maximum factor of n." This part I understand less, especially how it relates to finding prime numbers. The instructions go on to say that I will use modulus on these inner loop values to determine if prime. I understand that when using modulus on my tested number with another number that isn't 1 or itself and it equals 0 that it can't be a prime number, but given the instructions thus far, I don't see where this second number is coming from.

Could someone please explain this algorithm outside of the context of programming?

I've been trying to write down on paper how an example might play out using a small prime number: 7. But I'm so confused that I'm questioning my interpretation of the instructions.

[JLBorges]

To test if n (positive n) is a prime number using trial division:

1. if( n == 2 ) n is prime
2. else if( n%2 == 0 ) n is not prime (even numbers greater than 2 are not primes)

3. else (n is an odd number greater than 2)
      we need to test for divisibility by trial division. 
      if n is not prime, then n == a*b, for some a and b
      the smaller of the two factors a and b would be <= square root of n 
      (the worst case is when a==b and n is a perfect square n == a*a)
      ergo we need to only check for divisibility by numbers up to the square root for n  
      ie. "The inner loop will iterate from 2 to floor( sqrt(n) )" 
      refining it: The inner loop will iterate from 3 up to, including, floor( sqrt(n) + 0.5 ) in steps of 2
      ( steps of 2: 3, 5, 7, etc. because we have already taken care of even numbers greter than 2) 
      (+ 0.5 is being ultra-defensive: take care of possible inaccuracies in the floating point computation of sqrt)

[atmetal]

Ok, that definitely explained it much better. I'll see if I can write the code now. Just in case I run into some trouble there, I'll avoid marking this as solved for now so that I can avoid starting multiple threads.

[icy1]

Also, this is a classic that will help you https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Imagine translating "Overview" into code, and also look at "Pseudocode" section. And the little .gif there in the wiki page explains visually how it works. I could come up with some code, but it'd be better if you go through the journey ;P

If you have trouble with logical or syntactical bugs, feel free to post here with your attempt.

[atmetal]

Code works. Glad I asked, because stumbling my way through that at my level of skill with C++ would have had me trying to diagnose twice as many potential issues (the code and the algorithm). Thanks again for your help.

[jonnin]

gcd of number & factorial(sqrt(number)) will also work, but the factorials get too large to deal with in a hurry. Its very fast and an interesting approach to the problem, but not terribly practical.