Chinaunix首页 | 论坛 | 博客
  • 博客访问: 303215
  • 博文数量: 105
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1569
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-21 00:58
  • 认证徽章:
个人简介

锻炼精神,首先要锻炼肉体

文章分类

全部博文(105)

文章存档

2018年(1)

2016年(1)

2015年(102)

2014年(1)

我的朋友

分类: C/C++

2015-11-15 10:56:26

题目链接:http://www.nowcoder.com/pat/6/problem/4079

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

如果是时间上加以限制的话,即求取多组范围内的素数,可以使用打印素数表的方法,生成一次,多次访问。
如果是空间上加以限制的话,即存放 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循环
 
   }

}



题目代码:

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string.h>
  4.  
  5. using namespace std ;
  6.  
  7.  int prime[10000],num = 0 ;
  8.  
  9.  void setPrime( int N ){
  10.   
  11.     int i = 2, j ;
  12.     bool flag ;
  13.  
  14.     memset( prime, 0 , 10000 ) ;
  15.  
  16.     while (1){
  17.      
  18.         flag = false ;
  19.  
  20.         for ( j = 2; j*j <= i; j++ ){
  21.  
  22.             if( i % j ==0 ){
  23.                 flag = true ;
  24.                 break ;
  25.             }
  26.         }
  27.  
  28.         if( !flag )
  29.             prime[num++] = i ;
  30.         if(num > N)
  31.             break ;
  32.  
  33.         i++ ;
  34.     }
  35.  
  36.  }
  37.  
  38.  
  39.  
  40. int main( void ){
  41.     int M,N ;

  42.     cin>>M;
  43.     cin>>N ;
  44.  
  45.     setPrime(N) ;
  46.  
  47.     for (int i = M-1 ; i < N ; i++){
  48.         printf("%d", prime[i]) ;
  49.          
  50.         if( (i-M+2) % 10 ==0)
  51.             printf("\n") ;
  52.         else if(i != N-1)
  53.             printf(" ") ;
  54.     }
  55.   
  56.     return 0 ;
  57.  
  58. }

类似求素数题型汇总:


阅读(561) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册