プログラミング自主学習 DAY73 エラトステネスの篩

エラトステネスの篩

1を除外したすべての自然数は素数か、素数ではないか二種類だ。
素数は、1と自分のみを約数にもっている数だ。

自然数Nまでの素数の数、どの素数があるかを簡単に得られるアルゴリズムがある。
エラトステネスの篩というアルゴリズムだ。

public class SieveofEratosthenes {
   
static boolean prime[] = new boolean[11];   
//indexとの連携のため、0も含める。 そのゆえ、N+1の大きさを設定する。
	
public static void main(String[] args) {
		
int N = 10; 
		
prime[0]=prime[1]=true;   
//prime[0] <- 0  prime[1] <-1を意味する。 0,1は定義上、素数になれないため、trueにする
		
		
//2からN^1/2回る。約数を対象であるためだ。
for(int i=2; i*i<=N; i++ ) {
//初期値がfalseであるため、すべての要素を回る。
   if(!prime[i]) {
	for(int j=i*i; j<=N; j+=i) prime[j]=true;	  
	}
 }
 

i=2 j=4 -> prime[4]= true
i=2 j=6 -> prime[6]= true
i=2 j=8 -> prime[8]= true
i=2 j=10 -> prime[10]= true
i=3 j=6 -> prime[6]=true overwrite
i=3 j=9 -> prime[9]= true
i=4 16(i*i) > 10(N) finish!
残りのfalseは、素数だ。

for(int i=2; i<=N; i++) {
   	if(!prime[i]) System.out.println(i);
   }

iはインデックスをマッピングするように設定したため、これにより、個数と素数をプリントすることができる。