My version is divide only odd numbers by those already calculated prime numbers.

int n = 1000; int half = n/2; //At most n/2 prime numbers but when n is realy big this speculation is far from the accually size which is a waste(any way to solve it?) int* temp = new int[half]; int count = 0; if (n>3) { count = 3; temp[0]=1; temp[1]=2; temp[2]=3; for (int x=5;x<=n;x=x+2) { int y; for(y =1; y<count;y++){ if (x%temp[y] == 0) { //x is not a prime number y = count+1; break; } } if (y == count) { //x is a prime number temp[count] = x; count++; } } }else{ count = n; for (int x=0;x<n;x++) { temp[x] = x+1; } } // create another array which has the exact size as needed then delete the temp int* p = new int[count]; for (int z = 0; z<count; z++) { p[z] = temp[z]; } delete [] temp;

Any problem with this one or any faster way?