백준 1929 c++

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

 

 

 

일단 전의 보수문제에서 한단계 업그레이드 된거네?

그럼 일단 보수들을 전부뽑는 변수를 만들고

 

입력한 M과 N 사이의 값만 가져오게 하면 될거같은데..

 

 

보수는 자기자신과 1로만 되는거 전부다 나누었을때 총 2번만 나누어지면 된다.

 

 

 

for문을 두번써야할거같다.

 

정수 1부터 1000000 까지 돌리면서 또 안에 for 문으로 나머지연산자를 통해  소수를 구하면 될거같은데..

 

 

 

 

 

 

 

#include <iostream>

using namespace std;

int main() {

 

int dec[];

int M,N;

cin>>M;

cin>>N;

int cnt;

 

for(i=1;i<=1000000;i++){

for(n=1;n<=i;n++){

 

if( i%n==2){

dec[] = i;

}

 

cout<<M<dec[]<N;;

 

}

 

}

 

 

 

 

}

 

일단 내가 구상한 알고리즘

 

 

 

에러가 겁나게 뜬다...

 

 

chatgpt형님의 기술을 빌려 에러를 고쳐보자.

 

 

 

 

 

#include <iostream>

using namespace std;

int main() {

 

int dec[1000000]; // 여기를 안에 넣어서 초기화 시켜주는구나 배열크기를.

int M, N;

cin >> M; // Input value for M

 

cin >> N; // Input value for N

 

int cnt;

 

for (int i = 1; i <= 1000000; i++) {

for (int n = 1; n <= i; n++) {

 

if (i % n == 2) {

dec[cnt] = i; // dec안에 배열에 +cnt 를 넣고  i를배열에 넣은후  ++ 를 하여 배열칸의 순서를 다음칸으로 넘긴다.

cnt++;

 

}

 

 

cout << M << dec[cnt] << N; // 이게 아닌데...

 

 

}

 

}

 

return 0;

}

 

 

 

 

 

 

 

 

cout << M << dec[cnt] << N; // 이게 아닌데...

 

이 부분의 알고리즘을 수정해보자.

 

 

for(k=M; k<=N; k++) // i의 시작은 M 이고 점점 ++ 되면서 N까지 돌린다.

{

for(j=0;j<cnt.length;j++){

if()

}

}

 

 

아 모르겠다.   걍 해설 봐야겠다 후. 많이생각했어.

 

 

 

 

 

 

 

 

 

정답

 

 

 

#include <iostream>
using namespace std;

#define MAX 1000000

int arr[MAX + 1]{ 0, };

int main()
{
    int m, n;
    cin >> m >> n;

    for (int i = 2; i <= n; i++)
    {
        arr[i] = i;
    }

    for (int i = 2; i * i <= n; i++)
    {
        if (arr[i] == 0)
        {
            continue;
        }
        for (int j = i * i; j <= n; j += i)
        {
            arr[j] = 0;
        }
    }

    for (int i = m; i <= n; i++)
    {
        if (arr[i] != 0)
        {
            cout << arr[i] << '\n';
        }
    }
    return 0;
}

 

#define Max 10000000 으로 최대치를 정의했고..

int arr[Max+1]{0,};       //{0,} 이 뭔가 했더니 배열의 모든 수를 0 으로 초기화 해주는거네 ㅋㅋ 굿

 

 

 for (int i = 2; i <= n; i++)
    {
        arr[i] = i;
    }

 

arr[i] = i ;     //for 문을 돌리면서 i번째 배열에 넣으면서 쭉쭉 넣는다. n까지만.

내가 했던 방법은 최적화가 안되어있었을것이다.

 

 

 

 

 for (int i = 2; i * i <= n; i++)
    {
        if (arr[i] == 0)
        {
            continue;
        }
        for (int j = i * i; j <= n; j += i)
        {
            arr[j] = 0;
        }
    }

이건 뭔지 이해가 도저히안되네.

뭔가 했더니

에라토스테네스의 체<< 라는 소수구하는 공식을 이용한거였다. 공부하자!

 

 

 

 for (int i = m; i <= n; i++)
    {
        if (arr[i] != 0)
        {
            cout << arr[i] << '\n';
        }
    }
    return 0;

m부터 n까지 한번씩 돌려서

 

배열에서 0이 아닐경우 출력을 시킨다.

 

 

 

 

 

 

 

 

 

 

느낀점

엄청 머리를 쥐어짜내 만들었지만 오류투성이에 최적화도안되어있고 원하는 답도 안나왔다.

나도 언젠간 성장할수있을까 ㅠ