-2
#include <bits/stdc++.h> 
    using namespace std;
  
void SieveOfEratosthenes(int n) 
{ 
 
    bool prime[n+1];
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 

        if (prime[p] == true) 
        { 

            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 

    int index = 0;
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
       {
        index += 1;
            if(index % 100 == 1)
            {
                cout << index << ". " << p << endl;
                
            }
            
       }
           
} 
   
int main() 
{ 
    
    SieveOfEratosthenes(1000000); //if i add another 0 on this function the code won't run
    return 0; 
}

I am trying to create a program that prints out all prime numbers in increments of 100, starting from 1. First print out the 1st prime number, then the 101st, then 201st, 301st, and so on until the prime number is less or equal to 10^8. However, I can't do that because the program stops printing the number after some time because of what I assume is the memory limit on the array. Is there any way I could further increase these limits so I can print out more prime numbers up to 10^8?

Example of output:

1. 2
101. 547
201. 1229
301. 1993
401. 2749
501. 3581
601. 4421
701. 5281
801. 6143
901. 7001
1001. 7927
1101. 8837
1201. 9739
1301. 10663
1401. 11677
//..... (and so on until,)
78301. 997219
78401. 998617 // it stops here
AB3
  • 67
  • 6
  • 3
    Did you try using `std::vector` to save memory, and to avoid using stack? Note that VLA are not standard C++ – Damien Sep 26 '20 at 10:54
  • @g_bor Unsigned long long, won't that just affect the limit on the actual value inside the array and not the amount of data stored inside? – AB3 Sep 26 '20 at 10:55
  • Note that `memset(prime, true, sizeof(prime)); ` does not fill the array with `true`. If the size of a `bool` is four (which is common), it's filled with 4369. Use `std::fill`. – molbdnilo Sep 26 '20 at 11:10
  • 1
    `bool prime[n+1]` is not C++. Even if it was, you will blow up your stack. – Quimby Sep 26 '20 at 11:12
  • This doesn't address the question, but `if (prime[p] == true) ` is redundant. `if(prime[p])` says the same thing. – Pete Becker Sep 26 '20 at 15:12
  • Tangential: Take a look at https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h and https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice and maybe reconsider the first two lines of your code. – Nathan Pierson Sep 26 '20 at 16:19

1 Answers1

0

The logic is just wrong. Instead of using a massive array of bools to flag all numbers in the range (which will run out of memory whenever you try an extremely large range), simply use an array of integers with enough elements to cater for the expected number of primes and store the resulting integers within.

This is best done using a vector e.g. std::vector<unsigned long long>. If you're not using c++11+, you may be looking at using malloc and realloc to grab, reserve and resize your results list.

Den-Jason
  • 2,395
  • 1
  • 22
  • 17