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?