I am trying to understand the "Sieve of Eratosthenes". Here is my algorithm (code below), and a list of features that I cannot understand (in order).
- Why is
i * imore efficient thani * 2? Yes, I can understand it would be less iterations, therefore more efficient, but then doesn't it skip some numbers (for examplei = 9=>j = 81skips 18 27 36 ...)? - On Wikipedia I found that space complexity is equal to
O(n)and that's understandable; whatever number we enter it creates an array of the size entered, but time complexity here is where things get confusing. I found this notationO(n(logn)(loglogn))-- what is that? According to my understanding we have 2 full iterations and 1 partial iteration, thereforeO(n^2 * logn).
#include <iostream>
using namespace std;
int main() {
cout << "Enter number:" << endl;
int arrSize;
cin >> arrSize;
bool primesArr[arrSize];
primesArr[0] = false;
for (int i = 1; i < arrSize; i++) primesArr[i] = true;
for (int i = 2; i < arrSize; i++)
if (primesArr[i - 1]) {
cout << i << endl;
/* for (int j = i * 2; j < arrSize; j += i) less efficient */
for (int j = i * i; j < arrSize; j += i)
primesArr[j - 1] = false;
}
return 0;
}
ihave already been eliminated in the previous iterations. Thus,i * iis the smallest multiple ofithat hasn't been eliminated yet. (Write down the numbers from 1 to 100 on paper and execute the algorithm by hand to see it.)i * iquestion, it doesn't skip anything, because every number less thani^2is either prime or has a prime factor less thaniand has therefore already been marked at a previous step.