TopCoder 練習 PrimeSequences(Member SRM 471 Div1 Easy)

PrimeSequences(Member SRM 471 Div1 Easy)

■問題
ある自然数nについて，
n,[n/2],[[n/2]/2],[[[n/2]/2]/2],…
を考える．数列の第1項から連続した素数の個数が少なくともDである数の内，N以下で最大のものを計算せよ．

■解法
ほぼやるだけ．Nがそれ程大きくないので，素数全列挙で大丈夫でした．

import java.util.*;
import java.lang.*;

public class PrimeSequences{
 public int getLargestGenerator(int N, int D){
  int max=10000000;
  boolean[] ps=new boolean[max+1];
  Arrays.fill(ps,true);
  ps[0]=ps[1]=false;
  for(int i=2;i<=10000000;i++){
   if(ps[i]){
    for(int j=2;i*j<=10000000;j++){
     ps[i*j]=false;
    }
   }
  }
  int[] a=new int[max+1];
  for(int i=2;i<=max;i++){
   //System.out.println(i+":"+ps[i]);
   if(ps[i]&&a[i]==0){
    int k=1;
    for(int j=i;j<=max&&ps[j];j=j*2+1){
     a[j]=k++;
    }
   }
  }
  int ret=-1;
  for(int i=0;i<=N;i++){
   //System.out.println(i+":"+a[i]);
   if(a[i]>=D){
    ret=i;
   }
  }
  return ret;
 }
}