a121: 質數又來囉

內容 ：

你的好朋友質數先生又來找你囉，給你兩個數字，請算出這兩個數字包含的範圍內有幾個質數。

輸入說明 ： 

輸入兩個正整數a,b(1<=a<=b<=100000000)。
 保證b-a<=1000 

輸出說明 ： 

輸出一個非負整數，代表a到b之間(包含a,b)總共有幾個質數。

範例輸入 ： 

3 7
6 6
30 50

範例輸出:

3
0
5

提示 ： 

標籤:

數論

import java.util.Scanner;

public class a121 {

public static void main(String[] args) {

Scanner sc= new Scanner(System.in);    

        while(sc.hasNext()){

        int n,m,count=0;

        n=sc.nextInt();

        m=sc.nextInt();

        for(int i=n;i<=m;i++){

        if(run(i)==true)

         count++;

        if(i==2||i==3)

        count++;

        if(i==1)

        count--;

        }

        System.out.println(count);

        }

} 

public static boolean run(int n){

if(n%2==0)

return false;

if(n%3==0)

return false;

for(int i=3;i*i<n;i+=6){

if(n%(i+2)==0)

return false;

if(n%(i+4)==0)

return false;

}

return true;

}

}