1억 까지의 소수 구하기(C++)

#include <iostream>
#include <cmath>
#include <windows.h>
using namespace std;

int main(){
   
    int n,i,j,k=0,p=1,a[10000];
    bool sosu;
       
    cin>>n;
   
    a[0]=2;
   
    if(n>=2){
            cout<<2<<" ";
            k++;
    }   
    for(i=3;i<=n;i+=2){
                      sosu = true;
                      for(j=0;a[j]<=sqrt(i);j++){//sqrt는 <cmath>의 함수이다.
                                              if(i%a[j]==0){
                                                         sosu = false;
                                                         break;
                                              }
                      }
                      if(sosu){
                               cout << i <<" ";
                               if(p<10000){
/*a[10000] 부터는 i가 입력 되어선 안된다. 10000번째 소수는 적어도 10000보다 크므로 1억 이하의 소수를 구하는 과정에서는 문제가 없다.*/
                                            a[p++]=i;
                               }
                               k++;
                      }
                     
                      if(k==10){
                                cout << endl;
                                k=0;
                      }
    }
   
    system("PAUSE");
   
    return 0;
}
결과

100000000
     .
     .
     .

99998111 99998147 99998191 99998207 99998231 99998251 99998257 99998291 99998299 99998323
99998357 99998363 99998377 99998413 99998417 99998429 99998441 99998447 99998449 99998473
99998491 99998497 99998513 99998543 99998551 99998557 99998603 99998609 99998611 99998663
99998749 99998783 99998797 99998819 99998851 99998869 99998891 99998909 99998929 99998933
99998953 99998971 99998999 99999043 99999073 99999077 99999079 99999089 99999103 99999113
99999131 99999157 99999167 99999187 99999217 99999247 99999257 99999259 99999307 99999323
99999329 99999343 99999353 99999373 99999401 99999437 99999439 99999481 99999509 99999517
99999539 99999541 99999547 99999551 99999563 99999587 99999589 99999611 99999617 99999623
99999643 99999677 99999703 99999721 99999773 99999787 99999821 99999827 99999839 99999847
99999931 99999941 99999959 99999971 99999989 Press any key to continue . . .

계산 시간은 11분 정도 소모되었다.