[백준] 1644번 소수의 연속합 (gold 3

import java.io.*;
import java.util.*;


public class Main {
   public static void main(String[] args) throws IOException {
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
       int n=Integer.valueOf(br.readLine());
       boolean[] num=new boolean[n+1];

       int answer=0;
       HashMap<Long,Integer> dict=new HashMap<>();
       long sum=0;
       dict.put(0l,1);

       for(long i=2; i<=n; i++){
           if(num[(int)i]==true){
               continue;
           }
           sum+=i;
           dict.put(sum,1);
           if(dict.get(sum-n)!=null){
               answer++;
           }
           for(long j=i*i; j<=n; j+=i){
               num[(int)j]=true;
           }
       }
       bw.write(answer+"");
       bw.flush();
   }
}