[蓝桥杯]PREV-10.历届试题_幸运数

问题描述

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成

。

首先从1开始写出自然数1,,,,,,....

 就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除，变为：

 _  _  _  _  ....

把它们缩紧，重新记序，为：

     .... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，, , ...

此时7为第3个幸运数，然后再删去序号位置能被7整除的(,,...)

最后剩下的序列类似：

, , , , , , , , , , , , , , , , , , , , ...

输入格式

输入两个正整数m n, 用空格分开 (m < n < *)

输出格式

程序输出 位于m和n之间的幸运数的个数（不包含m和n）。

样例输入1

样例输出1

样例输入2

样例输出2

题目描述

代码如下：

 #include <stdio.h>

 #define MAX 1000*1000

 int m,n;

 int a[MAX+];

 void dp(int luck)

 {

     int i,cur = luck;

     if (a[luck] > n)

         return ;

     for (i=luck ; i<n ; i++) //遍历获取幸运数数列

     {

         if (i%a[luck] != )//序号位置是否能被幸运数整除

             a[cur++] = a[i];

     }

     dp(luck+);

     return ;

 }

 int main(void)

 {

     int i,ans;

     scanf("%d%d",&m,&n);

     for (i= ; i<=n ; i++)

         a[i] = i*-;

     dp();    //以第二个幸运数开始

     ans = ;

     for (i= ; a[i]<n ; i++)

     {

         if (a[i]>m)

             ans ++;

     }

     printf("%d",ans);

     return ;

 }

C解法

解题思路：

首先记录幸运数2时的数列(奇数列)，然后遍历2~n的幸运数，获得最终的数列

最后查找在区间[m,n]的数字个数。