[白俊]#1644少数の連合
10834 ワード
質問する
1つ以上の連続する少数の和が表すことができる自然数がある.いくつかの自然数の例を挙げると以下のようになります.
自然数が与えられた場合、連続する小数の和で自然数を表すことができる場合は、プログラムを作成して解きます.
入力
最初の行は自然数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);
}
}Reference
この問題について([白俊]#1644少数の連合), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준1644-소수의-연속합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol