[ Back to the overview Matrix ]

Test case : Prime Numbers using C++

Lines used: 44
// Prime numbers // Submission for Andreas practical language comparison // Compiles with gcc 3.2: g++ gprime.cpp -O -ogprime // Time to compute gprime 100000 : 0.85s on Athlon 2400 // Computes prime[1000000] in 13.8s // Lines used: 43 non-comment lines



#include <iostream>
#include <vector>


class Primes
{
    std::vector<int> primes;
    int n, sqrt_n;

    bool testPrime() const
    {
        for(int i=0; i<primes.size() && primes[i]<=sqrt_n; ++i)
            if(n%primes[i]==0) return false;
        return true;
    }

public:
    Primes() : n(2), sqrt_n(1)  { }

    int operator()()
    {
        if(n==2) { n=3; return 2; }     // The only even prime number

        for(;;n+=2)
        {
            while(sqrt_n*sqrt_n<n) ++sqrt_n;    // Maintain the square root

            if(testPrime())
            {
                primes.push_back(n);    // Add it to the list of primes
                n+=2;
                return n-2;
            }
        }
    }

    int operator[](unsigned n)
    {
        if(!n) return 2;
        while(primes.size()<n) operator()();
        return primes[n-1];
    }
};


int main(int argc, char**argv)
{
    Primes primes;
    int n = argc==2 ? atoi(argv[1]) : 1000;

    // Print the first n numbers in the stream
    for(int i=0; i<n; ++i)
        std::cout << primes[i] << " ";

    return 0;
}

Contributed by Calum, calum.bulk at ntlworld.com