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がそれ程大きくないので，素数全列挙で大丈夫でした．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class PrimeSequences{  
5.  public int getLargestGenerator(int N, int D){  
6.   int max=10000000;  
7.   boolean[] ps=new boolean[max+1];  
8.   Arrays.fill(ps,true);  
9.   ps[0]=ps[1]=false;  
10.   for(int i=2;i<=10000000;i++){  
11.    if(ps[i]){  
12.     for(int j=2;i*j<=10000000;j++){  
13.      ps[i*j]=false;  
14.     }  
15.    }  
16.   }  
17.   int[] a=new int[max+1];  
18.   for(int i=2;i<=max;i++){  
19.    //System.out.println(i+":"+ps[i]);  
20.    if(ps[i]&&a[i]==0){  
21.     int k=1;  
22.     for(int j=i;j<=max&&ps[j];j=j*2+1){  
23.      a[j]=k++;  
24.     }  
25.    }  
26.   }  
27.   int ret=-1;  
28.   for(int i=0;i<=N;i++){  
29.    //System.out.println(i+":"+a[i]);  
30.    if(a[i]>=D){  
31.     ret=i;  
32.    }  
33.   }  
34.   return ret;  
35.  }  
36. }  

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;
 }
}