C和指针之用拉托斯特尼筛方法(Eratosthenes)查找区间质素个数

   

    

     

      

     
     

      

       #include <stdio.h>
      
     
    

     

      

     
     

      

       #define LEN 10000
      
     
    

     

      

     
     

      

       /**
      
     
    

     

      

     
     

      

        *Eratosthenes-埃拉托斯特尼筛方法找质数，给出要筛数值的范围n，先用2去筛，2的倍数不是质数，
      
     
    

     

      

     
     

      

        * 再用下一个素数，也就是3筛，把3留下，把3的倍数不是质数，接下去用下一个素数5筛，把5留下，把5的倍数不是质数，
      
     
    

     

      

     
     

      

        *c不断重下去......
      
     
    

     

      

     
     

      

        * 求区间质素个数
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int get_all(char *a, int start, int end)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

          if (end > LEN)
      
     
    

     

      

     
     

      

        return 0;
      
     
    

     

      

     
     

      

          int count = 0;
      
     
    

     

      

     
     

      

          //初始化，把每个元素设置'1'
      
     
    

     

      

     
     

      

          for (int i = start; i < end; i++)
      
     
    

     

      

     
     

      

        *(a + i) = '1';
      
     
    

     

      

     
     

      

        //把下标不是质素的数组元素设置为‘0’
      
     
    

     

      

     
     

      

        for (int i = 2; i * i <= end; ++i)
      
     
    

     

      

     
     

      

        if (*(a + i) == '1')
      
     
    

     

      

     
     

      

        for (int j = 2; j * i < end; ++j)
      
     
    

     

      

     
     

      

        *(a + i * j) = '0';
      
     
    

     

      

     
     

      

        //打印质数
      
     
    

     

      

     
     

      

        for (int i = start; i < end; ++i)
      
     
    

     

      

     
     

      

        if (*(a + i) == '1')