[伯俊C+]1644少数の連続和

質問する

1つ以上の連続する少数の和が表すことができる自然数がある.いくつかの自然数の例を挙げると以下のようになります.
3:3(1種)
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つの数が出力される.
https://www.acmicpc.net/problem/1644

に答える

制限時間が2秒の場合、Nの最大値は400万であるため、連続する小数和(自己を含む400万)を算出するには400万以下のすべての小数を求める必要がある.
ここでは,一般的な方法の小数を求めるアルゴリズムよりも,エラトネスの体法を用いて小数を求めるべきである.

注意:https://marobiana.tistory.com/91
このブログの内容を見ると、5万種類の時は0.006秒.400万ぐらいなら、1秒で少数を救うのに十分です.
こうして求めた少数はdequeに組み込まれた.これは、400万個の小数点を求めると、ベクトルを使用するとメモリレプリケーションプロセスのオーバーヘッドが増加するためです.頻繁に挿入していたので選びました.
この小数点リストの最初の部分から最後まで、0番目の要素からn番目の要素へのインデックスを開始し、連続和を順次求める.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using namespace std;
//prime : 2부터 num까지 모든 숫자 기록
//primeList : 2부터 num까지의 소수 만 기록
deque<bool> prime; 
deque<int> primeList;

void findPrime(int num) {
	prime.push_back(false); //1, 2, 3, ... , num
	int cnt = num;
	while(cnt--)
		prime.push_back(true); //모든요소를 true로 초기화
	for (int i = 2; i * i <= num; i++) { //소수를찾음
		if (!prime[i]) continue;
		for (int j = i + i; j <= num; j += i) 
			//i를 제외한 i의배수들을 전부 소수가아님을check
			prime[j] = false;
	}
	for (int i = 2; i <= num; i++)
		if (prime[i]) primeList.push_back(i);
}

int find(int num) {
	int res = 0;
	for (int i = 0; i <= primeList.size(); i++) { //소수갯수만큼반복
		//i인덱스로 시작되는 소수(2,3,5,7...)를 탐색
		int j = i; //현재 탐색중인인덱스 (i, i+1, i+2...)
		int sum = 0;
		int primeCnt = primeList.size() - i; //소수리스트 최대길이만큼반복
		vector<int> temp;
		//i + (i+1) + (i+2)... 해서 연속소수의합이 소수가되는지확인
		while (primeCnt--) { 
			sum += primeList[j]; //소수의합을 기록
			temp.push_back(primeList[j]); //디버깅용
			if (num == sum) { //연속소수합이 소수가되는경우
				res++; //찾음+1
				sum = 0; //합초기화
				break;
			}
			else if (num < sum) { //소수합 소수를넘어선.. 오류난경우
				sum = 0; //합초기화
				break; //합이 더 커지면 끝
			}
			j++; //다음 인덱스 탐색
		}
		//여기로오면 다음 i+1번째를 시작인덱스로 찾으러감
	}
	return res;
}

int main(void) {
	int N;
	scanf("%d", &N);

	findPrime(N);
	printf("%d", find(N));

	return 0;
}