你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：幸運數

幸運數是波蘭數學家烏拉姆命名的，它采用與生成素數相同的“篩法”生成

首先從1開始寫出自然數1、2、3、4、5、6......

1就是第一個幸運數

我們從2這個數開始，把所有序號能被2整除的項洗掉，變為：

1_3_5_7_9.......

把他們縮緊，重新記序，為：

1 3 5 7 9......這時3為第二個幸運數，然后把所有能被3整除的序號位置的數刪去，

注意：是序號位置，不是那個數本身能否被3整除！！整除的應該是5、11、17...

此時7為第三個幸運數，然后再刪去序號位置能被7整除的（19、39...）

最后剩下的序列類似：

1、3、7、9、13、15、21、25、31、33、37、43、49、51、63、67、69、73、75、79......

本題要求：

輸入兩個正整數m n，用空格分開，（m<n<1000*1000）

程式輸出位于m和n之間的幸運數的個數（不包含m和n）

例如：

用戶輸入：

1 20

程式輸出：

5

例如：用戶輸入：

30 69

程式輸出：

8

解題思路：

本題在解題上，根據題意我們可以先獲取到經過一次篩選后得到陣列，即只有奇數的陣列，我們可以將該陣列作為起始陣列，根據幸運數的篩選規律，再進行之后的篩選，同時對于刪去的數，我們需要將之后沒有洗掉的數填補上去，直到幸運數字的下標是等于陣列的長度時，這個時候就不能夠再洗掉，然后從最終得到的陣列中找出在m和n之間的數的個數即可，

答案原始碼：

package 一三年省賽真題;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Year2013_Bt8 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		int n = scanner.nextInt();
		int[] arr = new int[n];
		//進行第一輪篩選，剔除所有的偶數
		for (int i = 0; i < n; i++) {
			arr[i] = 2*i+1;
		}
		
		int s = 1;	//記錄幸運數的下標
		while (s<=arr.length) {
			int p = s+1;	//記錄數前移到的下標
			for (int i = s+1; i < arr.length; i++) {
				//如果該數所處的序號能夠被幸運數整除
				if ((i+1)%arr[s]==0) {
					
				}else {	//如果該數所處的序號不能夠被幸運數整除，那么該數應該前移，
					arr[p] = arr[i];
					p++;
				}
				if (arr[i]>n) {
					break;
				}
			}
			s++;	//每排列一次，幸運數的下標加1
		}
		
		int count=0;	//記錄個數
		for (int i = 0; i < arr.length; i++) {
			if (arr[i]>m&&arr[i]<n) {	//找出位于m和n之間的幸運數，并記錄個數
				count++;
			}
			if (arr[i]>=n) {
				break;
			}
		}
		System.out.println(count);
	}

}