Print prime numbers less than 100

Question

Possible Duplicate:
Which is the fastest algorithm to find prime numbers?

is there any way to make this more optimize..

#include <vector>
    int main()
    {
        std::vector<int> primes;
        primes.push_back(2);
        for(int i=3; i < 100; i++)
        {
            bool prime=true;
            for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
            {
                if(i % primes[j] == 0)
                {
                    prime=false;
                    break;
                }
            }
            if(prime) 
            {
                primes.push_back(i);
                cout << i << " ";
            }
        }

        return 0;
    }

You could change the i++ part of your loop to i +=2 since we know all even numbers aren't going to be prime anyways — Akron, Nov 02 '11 at 18:13

Emil Sit · Answer 1 · 2011-11-02T21:47:35.590

11

int main(int argc, char *argv[]) {
    cout << "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ";
}

:-)

More seriously, you could avoid repeatedly squaring the primes by caching primes[j] * primes[j] and save on multiplications.

edited Nov 02 '11 at 21:47

answered Nov 02 '11 at 18:16

Emil Sit

22,894
7
53
75

What about 101, you forgot it! – Michael Goldshteyn Nov 02 '11 at 18:16
+1: A good answer for the given range. – Jørgen Fogh Nov 02 '11 at 18:17
haha, I like this response. It is truly the fastest way to output all primes under 100 – Akron Nov 02 '11 at 18:17
even the space at the end is there. nice :D – Karoly Horvath Nov 02 '11 at 18:17
4

But he asked to print 100 prime numbers, not prime numbers<100, even though that's what his program did! – Michael Goldshteyn Nov 02 '11 at 18:18
1

The OP's code contradicts the title. The OP wants to generate prime numbers under 100 it seems (?) unless the code/logic is wrong. – Marlon Nov 02 '11 at 18:19

score 4 · Answer 2 · answered Nov 02 '11 at 18:12

4

Sieve of Eratosthenes is a great algorithm for generating prime numbers up to a certain number (which is not what your title states, but what your code implies).

answered Nov 02 '11 at 18:12

Marlon

19,924
12
70
101

I don't think Sieve algorithm works better than nave algorithm in the case of numbers within [1..100] – Saeed Amiri Nov 02 '11 at 18:18
@SaeedAmiri Any reason why you don't think this? – Paŭlo Ebermann Nov 02 '11 at 18:32
@Paŭlo Ebermann, because there are to many number dividable to 2,3,5,7 in this range and you will check them multiple time, but by nave algorithm you skip this type of checking and because there are just 3,5,7 which should be checked in nave algorithm, there isn't to many performance issue in fact it's at most 150 checking, but in sieve algorithm I don't know how many checking should have but it should be more than 150, It's just guess it's not hard to compute it. – Saeed Amiri Nov 02 '11 at 18:40
@SaeedAmiri The proportion of numbers dividable by 2,3,5,7 are the same in greater ranges (1/2, 1/3, 1/5, 1/7), so I don't see why the sieve should get faster there. – Paŭlo Ebermann Nov 02 '11 at 19:49
@Paŭlo Eberman because in greater range bigger primes will be included in nave algorithm. in fact `sqrt n` and `log n` will have meaning there not here. (asymptomatic functions are can see there not in small range). – Saeed Amiri Nov 02 '11 at 19:57

score 1 · Answer 3 · answered Nov 02 '11 at 18:13

1

Yes, change i++ to i+=2 and it will work twice as fast.

answered Nov 02 '11 at 18:13

Michael Goldshteyn

71,784
24
131
181

no it won't... just microoptimization – Karoly Horvath Nov 02 '11 at 18:15
Why wouldn't it make it twice as fast, if you only test half the numbers? – Michael Goldshteyn Nov 02 '11 at 18:16
because you test it against the first prime, which is 2, exiting the loop immediately. – Karoly Horvath Nov 02 '11 at 18:16
true, you would stop the search early – Michael Goldshteyn Nov 02 '11 at 18:17
Or better, except for 2 and 3 all primes are of the form 6n ± 1. – Greg Hewgill Nov 02 '11 at 18:19
You can't know without profiling. :) It could well be that output itself is taking the majority of time here and you could make the program 2x faster, say, by replacing cout with printf. – UncleBens Nov 02 '11 at 21:27

score 1 · Answer 4 · answered Nov 02 '11 at 18:16

1

do not do primes[j]*primes[j] <= i just check primes[j] <= 7
use i+=2

answered Nov 02 '11 at 18:16

Saeed Amiri

22,252
5
45
83

Considering that `primes[3]==7`, it's even simpler to write `j <=3 `. (`primes[j] < 11` would be more obvious). – MSalters Nov 03 '11 at 12:22

Jørgen Fogh · Answer 5 · 2011-11-02T18:32:20.100

Yes. As Marion has suggested, you can use the Sieve of Eratosthenes but you should be aware of the details. The code you have written looks superficially like the sieve, but it isn't. It's called trial division and it has a different algorithmic complexity than the sieve.

The sieve performs a pass which takes Theta(n/p) time for each prime p. This results in a total complexity of O(n log log n). IIRC the proof is a bit complicated and involves the prime number theorem.

Your algorithm performs pi(sqrt(p)) divisions for each prime number p and a smaller number of divisions for non-primes. (where pi is the prime-counting function). Unfortunately I can't come up with the total complexity off the top of my head.

In short, you should change the code to use an array and mark all the non-primes. This article addresses the same topic in functional programming languages.

True. I apparently didn't think it through. – Jørgen Fogh Nov 02 '11 at 18:33 — Jørgen Fogh, Nov 02 '11 at 18:33

vudduu · Answer 6 · 2011-11-02T22:05:15.077

1

Yes, Sieve of Eratosthenes is the best option (If you need most than 100 numbers this is the best implementation). This is my implementation:

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

vector<int> sieve(int n){
    vector<bool> prime(n+1,true);
    vector<int> res;
    prime[0]=prime[1]=false;
    int m = (int)sqrt(n);
    for(int i=2; i<=m; i++){
        if(prime[i])
            for(int k=i*i; k<=n; k+=i)
                prime[k]=false;
    }
    for(int i=0; i<n ;i++)
        if(prime[i])
            res.push_back(i);
    return res;
}

int main(){
    vector<int> primes = sieve(100);
    for(int i=0; i<primes.size() ;i++){
        if(i) cout<<", ";
        if(primes[i]) cout<<i;
    }
    cout<<endl;
}

edited Nov 02 '11 at 22:05

answered Nov 02 '11 at 18:34

vudduu

167
9

An interesting question is whether using `vector` is faster than using, say `vector` (with 0 and 1 for false and true). `vector` certainly requires a lot of extra effort to read or write any single value, but `vector` will take 8 times more memory, reducing locality, and causing a lot more cache misses. – James Kanze Nov 02 '11 at 19:01
In C++ bools and chars use 8bits, but bool doesn't use all of them. – vudduu Nov 02 '11 at 19:32
In C++, the size of a `bool` or a `char` is implementation defined. I'm aware of machines today where `char` is 8, 9 or 32 bits, and `bool` can be a single `char`, or more---there are definitely systems where it is the same size as an `int` (4 or 6 bytes, on the two platforms I'm aware of where this is the case). None of which is relevant here, since `std::vector` is specialized to only use 1 bit per boolean value. Whence my comment. – James Kanze Nov 03 '11 at 08:58
1) http://stackoverflow.com/questions/2064550/c-why-bool-is-8-bits-long 2) http://stackoverflow.com/questions/4626815/why-is-a-boolean-1-byte-and-not-1-bit-of-size – vudduu Nov 16 '11 at 16:08
Interesting, because the answers in those two articles skirt around the issue. The reason why a `bool` is at least the size of a `char` is because the standard doesn't allow `sizeof(bool)` to be less than 1, and requires `sizeof(char)` to be 1. The addressing issues are motivation for this, somewhat; it would certainly be possible to generate code to address bits, if the standard allowed it, but it would be inefficient, and worse, would create no end of problems with `sizeof` and pointer arithmetic. – James Kanze Nov 16 '11 at 17:14

Print prime numbers less than 100

6 Answers6