[pat 解题报告]数素数

题目链接:

题目分析:
这道题算是素数考察的比较简单的题型，相对复杂的也有，一个是对该题型在时间上加以限制，另一个是在该题型的基础之上对空间加以限制。

如果是时间上加以限制的话，即求取多组范围内的素数，可以使用打印素数表的方法，生成一次，多次访问。
如果是空间上加以限制的话，即存放 10000 个素数的话，那筛选素数的数据范围至少是 2-10000^2 ,相关的数组访问范围就需要注意了。

在这道题上卡的时间比较久，原因是因为，一直想使用打表的方式来存储素数，导致数组范围出问题，想使用位图的解决方法，浪费了很多的时间。
后来，重新看了一遍题目，发现只对一组数据进行求取，所以打表就没有必要了。

求素数一共有2中方法，一种是埃氏筛选法，另一种是欧拉筛选法；
前者的时间复杂度大于后者，后者的时间复杂度较理想，但是空间复杂度稍大些

埃氏筛选法可以很好的与位图技术法结合使用，
而欧拉筛选和位图结合使用在实现方面较为复杂

在这里采用的是埃氏筛选法，算法的实现就是我们最普通的素数筛选法

void setPrime(int N){
 int i = 2 ; 
 bool flag  ;

 while(1){
    
     flag  = false ;

   // 无限制的将筛选出来的素数存放到 prime 数组中
     for ( int j = 2 ; j*j <= i; j++ ){
        if( i % j == 0){
              flag = true ;
               break ; 
      }

       if(!flag){
        prime[num++] = 0 ;
      }

       i++ ;

     if( num> N) break ; // 一旦 num 个数达到 N 个，则退出 while循环
 
   }

}



题目代码:

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std ;

 int prime[10000],num = 0 ;

 void setPrime( int N ){

    int i = 2, j ;
    bool flag ;

    memset( prime, 0 , 10000 ) ;

    while (1){

        flag = false ;

        for ( j = 2; j*j <= i; j++ ){

            if( i % j ==0 ){
                flag = true ;
                break ;
            }
        }

        if( !flag )
            prime[num++] = i ;
        if(num > N)
            break ;

        i++ ;
    }

 }



int main( void ){
    int M,N ;

    cin>>M;
    cin>>N ;

    setPrime(N) ;

    for (int i = M-1 ; i < N ; i++){
        printf("%d", prime[i]) ;

        if( (i-M+2) % 10 ==0)
            printf("\n") ;
        else if(i != N-1)
            printf(" ") ;
    }

    return 0 ;

}

类似求素数题型汇总: