# Find prime numbers from 1 to 100

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.

Do you think my codes are short, simple, efficient, and easy to understand?

#include <iostream>
#include <string>
#include <vector>

int main()
{
std::vector<int> primes = { 2 };
for (int i = 2; i <= 100; ++i)
for (int j = 2; j < i; ++j) {
if (i % j == 0)
break;
if (j == i - 1)
primes.push_back(i);
}
for (int x: primes)
std::cout << x << ' ';
return 0;
}

• @pacmaninbw Suggestions for improvements belong in answers, not comments. – 200_success Aug 12 '16 at 15:26
• Is this a homework question? – 200_success Aug 12 '16 at 15:28
• No, it is an exercise question from the book "Programming Principles and Using C++". I am doing self-learning. – Herman Tam Aug 12 '16 at 15:29
• Three words: "Sieve of Eratosthenes" – Martin York Aug 12 '16 at 19:09

• First suggestion: do a search before posting, there are many very similar questions on codereview.

• What the problem itself suggests is actually better than what you have, because it suggests you write a function to check if a number is prime, while you have everything patched together.

• So, the first step is, split the code and write a function that is something like bool is_prime(int input_number)

• Then, as said in the comments, you can stop at the square root of the number you're checking.

• You know that even numbers are not primes, so you can consider 2 the first prime, start the loop at 3 and increment by 2 instead of 1

• Your code will print an extra blank space at the end

• Just as an extra optimization, you can keep track of the primes that you've already found and use those to check, skipping what's in between, and continuing from there

Well, um

• Use some braces. Whilst it's perhaps excusable not to use braces for a one liner, you have a very long for loop without braces. That's asking for trouble in code that someone has to maintain.
• This is not re-usable. You should at least make this a function which can be called from main with the required maximum number.
• It'd go faster if you maintained your prime numbers during the calculation, in a vector or an unordered set (depending on how big you expect the table to get)