[Develog]Green-Tao Theorem, 소수등차수열 구현(1)

https://youtube.com/shorts/kzKt1jRsAIo?feature=share
위 영상을보고난뒤, 길이가 n인 소수등차수열은 정수범위에서 무조건 존재한다고 한다.
이를 직접 구현하여 해당하는 소수등차수열을 출력하도록 해보았다.

맨처음 고안한 프로그램 진행방향은

0. go : 찾은소수 리스트에서 탐색을 시작할 인덱스
   to : 찾은소수 리스트의 맨끝 인덱스
   chunk : 위와같은 인덱스이나 특정조건에서만 사용할것
   diff : 등차값. 1부터 시작하여 모든 소수를 탐색하며 점차 늘려나갈것이다.
   prime : 소수리스트 (벡터)
   result : 구하고자하는 소수등차수열에 해당하는 소수들을 담는 벡터
1. prime의 맨앞부터 맨뒤까지 등차수열을 만족하는것을 찾아갈것이다. 맨끝까지 탐색을 완료한경우, 등차값을 1 증가시키고 다시 반복할것.
   1-0. result가 비어잇으면 result에 prime[go]를 추가
   1-1. result의 요소가 n개면 출력한다.
2. 이전소수prime[go] 와 현재소수(prime[go+1])의 차이값과 현재 등차값을 비교
   2-1. 두값이 동일)) go++, result에 prime[go] 추가
   2-2. 차이값이 크다)) go++, result초기화
   2-3. 차이값이 작다)) 다음 소수를 탐색해야한다.
   chunk = go+2(하나를 건너띈것), 이전소수 prime[go]와 prime[chunk]간의 차이값과 등차값을 비교.
   2-4. 두값이 동일)) go를 chunk + 1로 이동, result에 추가
   2-5. 차이값이 크다)) go = chunk-1, result초기화
   2-6. 차이값이 작다)) chunk++
3. 탐색하다가 go > to 가되면 등차값++ 한뒤 반복
   3-1. 탐색중에 chunk > to 또한 등차값++ 하고 반복
4. 등차값이 특정값을넘어가면 find_prime실행 해야함.
   4-1. 등차값이 max_number보다크면 find_prime실행.
5. 사실 n >= 11이면 find_prime을 10번 실행시켜야함(최소 11만이상의소수필요)

이상태로 프로그램을 짜보았더니
1-0과 2-2를 번갈아 반복하더니 prime벡터의 아웃오브레인지 오류가 떴다.

다시살펴보니,
여기서 끝인덱스와의 '='을 빼먹어서 난 오류였다.
이제 실행해보았다.

n이 3일때는 정상이나, 4일때는 틀렸다.
정상적인 수순이면, 5, 11, 17, 23 일텐데 31부터인걸보면
소수를 건너띄는 과정(chunk를 사용하는)에서 오류가 난것같다.

이부분을 개선하려고했으나, 그냥 간단하게,
start 변수를 선언하여,
소수리스트의 맨처음요소부터 마지막요소까지
모두 한번씩 result의 첫요소에 들어가도록 하였다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; 
typedef unsigned long long llu;
llu max_number = 10001;
vector<llu> prime, result; //소수 리스트

bool isPrime(llu n) {
    for (llu i = max_number - 10000 + 1; i <= sqrt(n); i++) //전달받은 n의 제곱근 루트n을
        //루트n 보다 작은 정수 i들로 나누었을때 나눠떨어지면
        if (n % i == 0)
            return false; //소수가아니다.
    return true; //만약 모든 i가 나눠떨어지지않으면 소수인것
}
void find_prime(int n) { //n만개의 정수를 탐색하여 소수만 prime에 기록ㄴ
    while (n--) {
        for (llu i = max_number - 10000 + 1; i <= max_number; i++)
            if (isPrime(i))
                prime.push_back(i);
        max_number += 10000;
    }
}

void init() {
    find_prime(1); //처음엔 만개의 소수를 탐색

}

void logic(llu n) {
    if (n == 2) {
        printf("2  3  등차 : 1\n\n");
        return;
    }
    llu start = 0;
    llu go = 0; //소수리스트의 시작 인덱스
    llu chunk = 0; //소수를 건너띌때 사용할 인덱스
    llu diff = 2; //소수등차수열의 등차. 최솟값
    llu to = prime.size(); //소수리스트의 마지막 인덱스
    bool end = false;
    if (n >= 11 && max_number == 10001) {
        find_prime(10);
    }

    while (1) {
        if (go + 1 >= to || end) {  //현재 등차값으로 탐색을 완료했으면
            diff++; //등차값을 증가시키고
            start = 0;
            go = 0;  //다시 반복한다.
            result.clear();
            if (diff >= max_number) //등차값이 너무커지면 소수리스트를 갱신함.
                find_prime(3);
            to = prime.size();
            end = false;
        }

        if (result.size() == 0) {
            start++;
            go = start;
            result.push_back(prime[go]);
            continue;
        }
        if (result.size() == n) { //n개의 소수등차수열을 찾았다면
            for (llu i = 0; i < n; i++) { //출력
                printf("%llu  ", result[i]);
            }
            printf("등차 : %llu\n\n", diff); //출력
            result.clear();
            return; //종료
        }
        /////////////////////////////////////////////////////////////////
        //이전소수와 현재소수의 차잇값과 등차값을 비교
        if (prime[go + 1] - prime[go] == diff) { //같을때
            go++;
            result.push_back(prime[go]);
        }
        else if (prime[go + 1] - prime[go] > diff) { //차잇값이 더 클때
            if (result.size() == 1)
                go++;
            result.clear();
        }
        else { /////////////////////////////////////////////////////////////
            //등차값이 더 클때
            //현재소수 다음소수와 차잇값으로 등차값과 비교
            chunk = go + 2;
            while (1) {
                if (chunk >= to) {
                    end = true;
                    break;
                }
                if (prime[chunk] - prime[go] == diff) { //같을때
                    result.push_back(prime[chunk]); //찾은소수를 기록
                    go = chunk; //현재 찾은 소수를 이전소수로 기록(계속 반복할것이니까)
                    break; //찾은 소수를 기록
                }
                else if (prime[chunk] - prime[go] > diff) { //차잇값이 더 클때
                    go = chunk - 1;
                    result.clear();
                    break; //지금껏 찾은 소수들을 초기화하고 다시 진행한다.
                }
                else { //등차값이 더 클때
                    chunk++;
                }
            }
        }
    }
}

void func() {
    while (1) {
        printf("%s", "정수n 을 입력시 길이가 n인 소수등차수열을 출력합니다.");
        llu n;
        scanf("%llu", &n);
        logic(n);
    }

}

int main(void) {
    init();
    func();

    return 0;
}

다음으로는 각 소수를 구할때 걸리는 시간을 측정하도록 만들어볼것이다.