I am working on producing C++ code to list all primes between 1 and 100 say. In order to present my question I need to provide some background.
The basic idea of what I want to do is the following:
Introduce a vector to hold all the primes in ascending order. If the first j elements of this vector are given, the j+1 element is then given as the smallest integer larger than the j'th element which is not divisible by any of the first j elements. The first element is moreover given to be 2.
Thus if v denotes the vector of primes, I want to produce code which implements the following math-type argument;
v[1]=2;
for(2<i<=100)
if i % v[j] !=0 FOR ALL 0<j< v.size()
v.push_back(i)
else
do nothing
The problem I am facing however is that C++ doesn't seem to have a for all type language construct. In order to get around this I introduced a counter variable. More precisely:
int main() {
const int max=100;
vector<int>primes; // vector holding list of primes up to some number.
for(int i=2; i<=max;++i){
if(i==2)
primes.push_back(i); // inserts 2 as first prime
else{
double counter=primes.size(); // counter to be used in following loop.
for(int j=0;j<primes.size();++j){
if(i% primes[j]==0){
break; // breaks loop if prime divisor found!
}
else{
counter-=1; //counter starts at the current size of the primes vector, and 1 is deducted each time an entry is not a prime divisor.
}
}
if (counter==0) // if the counter reaches 0 then i has no prime divisors so must be prime.
primes.push_back(i);
}
}
for(int i=0; i<primes.size(); ++i){
cout << primes[i] << '\t';
}
return 0;
}
The questions I would like to ask are then as follows:
- Is there a for-all type language construct in C++?
- If not, is there a more appropriate way to implement the above idea? In particular is my use of the counter variable frowned upon?
- (Bonus) Is anyone aware of a more efficient way to find all the primes? The above works relatively well up to 1,,000,000 but poorly up to 1 billion.
Note I am beginner to C++ and coding in general (currently working through the book of Stroustrup) so answers provided with that in mind would be appreciated.
Thanks in advance!
EDIT:
Hello all,
Thank you for your comments. From them I learned that both use of a counter and a for all type statement are unnecessary. Instead one can assign a true or false value to each integer indicating whether a number is prime with only integers having a true value added to the vector. Setting things up in this way also allows the process of checking whether a number is prime given the currently known'' primes to be independent of the process of updating the currently known'' primes. This consequently addresses another criticism of my code which was that it was trying to do too many things at once.
Finally it was pointed out to me that there are some basic ways of improving the efficiency of the prime divisor algorithm for finding primes by, for instance, discounting all even numbers greater than 2 in the search (implemented by starting the appropriate loop at 3 and then increasing by 2 at each stage). More generally it was noted that algorithms such as the sieve of Erastothenes are much faster for finding primes, as these are based on multiplication not division. Here is the final code:
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int> primes; // vector holding list of primes up to some number.
bool is_prime(int n) {// Given integer n and a vector of primes this boolean valued function returns false if any of the primes is a prime divisor of n, and true otherwise. In the context of the main function, the list of primes will be all those that precede n, hence a return of a true value means that n is itself prime. Hence the function name.
for (int p = 0; p < primes.size(); ++p)
if (n % primes[p] == 0) {
return false;
break; // Breaks loop as soon as the first prime divisor is found.
}
return true;
}
int main() {
const int max=100;
primes.push_back(2);
for (int i = 3; i <= max; i+=2)
if (is_prime(i) == true) primes.push_back(i);
for(int i=0; i<primes.size(); ++i)
cout << primes[i] << '\t';
return 0;
}
I just have one additional question: I checked how long the algorithm takes up to 1,000,000 and the presence of the break in the is_prime function (which stops the search for a prime divisor as soon as one is found) doesn't seem to have an effect on the time. Why is this so?
thanks for all the help!