问题描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。
首先从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]的数字个数。

05-11 11:04