幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。
首先从1开始写出自然数1,2,3,4,5,6,....
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 ....
把它们缩紧，重新记序，为：
1 3 5 7 9 .... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ...
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...
1 import java.util.Scanner; 2 3 public class Main { 4 5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 int count = 0; 8 int m = in.nextInt(); 9 int n = in.nextInt(); 10 int[] a = new int[n]; 11 // 初始化 12 for (int i = 0; i < a.length; i++) 13 a[i] = i * 2 + 1; 14 // 获取1到n的幸运数 15 getLuckNumArr(a, 1, n); 16 // 统计 17 for (int i = 0; i < n && a[i] <= n; i++) { 18 if (a[i] > m && a[i] < n) 19 count++; 20 } 21 System.out.println(count); 22 } 23 24 static void getLuckNumArr(int[] a, int start, int end) { 25 int k = start; 26 int x = a[start]; 27 for (int i = start; i < end; i++) { 28 if ((i + 1) % x != 0) { 29 a[k] = a[i]; 30 k++; 31 } 32 } 33 if (x < end) { 34 getLuckNumArr(a, start + 1, end); 35 } 36 } 37 }
| 评测点序号 | 评测结果 | 得分 | CPU使用 | 内存使用 | 下载评测数据 |
|---|---|---|---|---|---|
| 1 | 正确 | 25.00 | 187ms | 23.41MB | 输入 输出 |
| 2 | 正确 | 25.00 | 140ms | 23.27MB | 输入 输出 |
| 3 | 正确 | 25.00 | 218ms | 23.34MB | 输入 输出 |
| 4 | 正确 | 25.00 | 312ms | 23.61MB | 输入 输出 |
原文：http://www.cnblogs.com/wuqianling/p/5369875.html