Number prime with c++, what is wrong with the code and how to optimize?

Question

I'm trying to figure this problem http://www.urionlinejudge.com.br/judge/problems/view/1032, where I need to find the prime numbers between 1 to 3501 the fastest way, since the time limit may not exceed 1 second.

The way I'm calculating these prime numbers is to check if they are prime until their square root, then eliminating the multiple of the first prime numbers [2, 3, 5, 7] to improve the performance of the algorithm. Yet, the time exceeds.

My code (takes 1.560s as the internal testing of the submission system)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <set>

using namespace std;

set<int> circ;
set<int> primes;

/* Calculate List Primes */ 
void n_prime(int qtd){
    int a, flag=1, l_prime = 1;
    float n;
    for(int i=0;i<qtd;i++){
        switch (l_prime){
            case 1:
                l_prime = 2;
                break;
            case 2:
                l_prime = 3;
                break;
            default:
                while(1){
                    flag=1;
                    l_prime+=2;
                    if(l_prime>7)
                    while(l_prime%2==0||l_prime%3==0||l_prime%5==0||l_prime%7==0) l_prime++;
                    n=sqrt(l_prime);
                    for(a=2;a<=n;a++){
                        if(l_prime%a==0){
                            flag=0;
                            break;
                        }
                    }
                    if(flag) break;
                }
        }
        primes.insert(l_prime);
    }
}

/* Initialize set with live's */ 
void init_circ(int t){
    circ.clear();
    for(int a=0;a<t;a++){
        circ.insert(a+1);
    }
}

/* Show last live*/
void show_last(){
    for(set<int>::iterator it=circ.begin(); it!=circ.end(); ++it)
        cout << *it << "\n";
}

int main(){
    int n = 0;
    clock_t c1, c2;
    c1 = clock();
    n_prime(3501);
    while(scanf("%d", &n)&&n!=0){
        init_circ(n);
        int idx=0, l_prime,count = 0;
        set<int>::iterator it;
        set<int>::iterator np;
        np=primes.begin();
        for(int i=0;i<n-1;i++){
            l_prime=*np;
            *np++;
            idx = (idx+l_prime-1) % circ.size();
            it = circ.begin();
            advance(it, idx);
            circ.erase(it);
        }
        show_last();
    }
    c2 = clock();
    printf("\n\nTime: %.3lf", (double)(c2-c1)/CLOCKS_PER_SEC);
    return 0;
}

Answer 1

The easiest way is the sieve of Eratosthenes, here's my implementation:

//return the seive of erstothenes
std::vector<int> generate_seive(const ulong & max) {
    std::vector<int> seive{2};
    std::vector<bool> not_prime(max+1);
    ulong current_prime = seive.back();
    bool done = false;
    while(!done){ 
        for (int i = 2; i * current_prime <= max;i++) {
            not_prime[i*current_prime]=true;
        }
        for (int j = current_prime+1;true;j++) {
            if (not_prime[j] == false) {
                if( j >= max) {
                    done = true;
                    break;
                }
                else {
                    seive.push_back(j);
                    current_prime = j;
                    break;
                }
            }
        }
    }
    return seive;
}

Generates all the prime numbers under max, BTW these are the times for my sieve and 3501 as the max number.

real    0m0.008s
user    0m0.002s
sys     0m0.002s

Answer 2

There is a better algorithm for finding primes. Have you heard about Eratosthenes and his sieve?

Also, you are using tons of STL (i.e. the set<>) as well as remainder operations in your code. This is simply killing the speed of your program.

Answer 3

Some basic advice, then a basic (albeit untested) answer...

The advice: If you have one resource that's very limited, take advantage of other resources. In this case, since time is limited, take up a lot of space. Don't dynamically allocate any memory, make it all fixed length arrays.

The way I would do it is simply to have one boolean array and apply Aristophanes' sieve to it:

void findPrimes(int cap) { // set to void for now, since I don't know your return type
    bool[] possibilities = new bool[cap + 1]; // has to be dynamic so that you can scale for any top
    possibilities[0] = false;
    possibilities[1] = false;
    int found = 0;

    for (int i = 2; i < cap; ) {
        ++found;
        for (int j = i + i; j < cap; j += i) {
            possibilities[j] = false;
        }
        do {
            ++i;
        } while (!possibilities[i]);
    }

    // at this point, found says how many you've found, and everything in possibilities that is true is a factor.  Just return it however you need.

I see aaronman beat me to the punch with the sieve idea. Mine is a slightly different implementation (more exactly resembles the original sieve, using only addition), and uses less dynamic memory, so I'm still submitting it.

Answer 4

You can get quite a nice speedup by preexcluding even numbers, just change your increment to i += 2 and make sure you don't omit 2 in your result array. You might even think about trying to preexclude multiples of 3, but that starts getting dirty. Something along the lines:

for(long i = 1; i < qtd; i += 6) {
    //check if i is prime
    //check if i+4 is prime
}

This should be enough to get you below the limit.

Answer 5

The sieve of Eratosthenes is the right way to do it, as others have suggested. But the implementations I saw here were very complicated. The sieve is extremely easy to implement. E.g.:

std::vector<int> get_primes(uint max) {
  std::vector<int> primes;
  std::vector<bool> is_composite(max+1,false);
  for (uint i = 2; i <= max; ++i) {
    if (!is_composite[i]) {
      primes.push_back(i);
      for (uint j = i+i; j <= max; j += i) {
        is_composite[j] = true;
      }
    }
  }
  return primes;
}

Answer 6

There are two big, technical performance drains in your code:

1. You insert your primes into a vector. Whenever the vector exceeds its allocated size, it will get a new, larger buffer, copy everything over, and delete the old one. new is very expensive in terms of performance, even more expensive than the copying involved. You can avoid this by telling the vector to reserve() enough space.

2. You use sqrt() in your inner loop. This too is a slow function, square the prime instead (takes only one cycle on modern hardware), it will be faster.