Count Prime of Runtime Error at 1500000 input


  • 0
    A

    Dear all, my code get runtime at input 1500000, I run it locally and it showed "segmentation fault" but I have no idea about it. Can anyone help me? Thanks.

    int countPrimes(int n) {
        int count = 0;
        int A[n];
        int i,j,k,m;
    
    for(m=0;m<=n;m++)
        A[m] = 0;
    
    for( i =2; i<=n;i++)
    {
            for( j=2; j<=n; j++)
            {
                    if(i*j > n || A[i*j] == 1) break;
                    else
                    {
                         A[i*j] = 1;           
                    }
                    
            }
    }
    
    for( k=2; k<=n; k++)
    {
            if(A[k] == 0)
            {
                 count = count + 1;           
            }
            
    }
    
    return count;
    

    }


  • 0
    L

    i learn somthing from your idea, and write my code.

    about segmentation fault , may be the n is too lage for array A[n].

    you can use pinter.

    about the for() cycyle , you might need to make the n more small.

    int countPrimes(int n) {
    int i,j,temp=0,_n;
    for(_n=0;_n*_n<n;_n++);
    int *An=malloc(n*sizeof(int));
    for(i=0;i<n;i++){
        *(An+i)=1;
    }
    for(i=2;i<=_n;i++)
        for(j=2;j<n/i+1;j++){
            if(i*j<n)
                *(An+i*j)=0;
        }
    for(i=2;i<n;i++)
        temp=temp+*(An+i);
    return temp;}

  • 0
    A

    hihi, I have a question about this
    for(i=2;i<=_n;i++)
    for(j=2;j<n/i+1;j++){
    if(i*j<n)
    (An+ij)=0;
    }

    why the outside for loop don't need "{" ??
    I'm confused and don't know why I added "{" it would be runtime error.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.