[白俊]#1644少数の連合

質問する

1つ以上の連続する少数の和が表すことができる自然数がある.いくつかの自然数の例を挙げると以下のようになります.

3:3(一種)

41:2+3+5+7+11+13=11+13+17=41(3種)

53:5+7+11+13+17=53(両方)

しかし、いくつかの自然数は連続的な少数の和で表すことができず、20は一例である.7+13を計算すると20ですが、7と13は連続していないので適切な表現ではありません.また、小数は1回の加算にしか使用できないため、3+5+7のような表現にも適していない.
自然数が与えられた場合、連続する小数の和で自然数を表すことができる場合は、プログラムを作成して解きます.

入力

最初の行は自然数Nを与える.(1 ≤ N ≤ 4,000,000)

しゅつりょく

最初の行が連続する小数の和で自然数Nを表すことができる場合、1つの数が出力される.

入力例1

20

サンプル出力1

0

入力例2

3

サンプル出力2

1

入力例3

41

サンプル出力3

3

入力例4

53

サンプル出力4

2

に答える

この問題はエラトネスのふるいで少数を求め,それから累積で問題を解くことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = N-1;

        boolean[] flag = new boolean[N+1];
        flag[1] = true;

        for(int i=2; i*i<=N; i+=1) {
            for(int j=i*i; j<=N; j+=i) {
                if(!flag[j]) {
                    flag[j] = true;
                    M--;
                }
            }
        }

        int[] arr = new int[M];
        int idx = 0;

        for(int i=2; i<=N; i++) {
            if(!flag[i]) {
                arr[idx] = i;
                idx++;
            }
        }

        int cnt = 0;
        for(int i=0; i<M; i++) {
            int sum = 0;

            for(int j=i; j<M; j++) {
                sum += arr[j];

                if(sum==N) {
                    cnt++;
                    break;
                }

                if(sum>N) break;
            }
        }

        System.out.println(cnt);
    }
}