백준(baekjoon)(BaekJoon)코딩 1929번:에라토스테네스의 체 답

// 1000이하의 소수들의 배수에 속하지 않아야 소수가 나온다

// 최종으로 구한 소수 중 N,M사이에 있는 소수만 출력해야한다

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int M, N, cnt = 0, p = 0, total = 0;
 
cin >> M >> N;
int *arr = new int[N - M + 1];
for (int i = M; i <= N; i++)
{
arr[p] = i;
p++;
}
p = 0;
for (int i = 2; i <= sqrt(N); i++)
{
for (int j = 0; j < N - M + 1; j++)
{
if(arr[j]==-1)
{
continue;
}
if (arr[j] % i == 0 && arr[j] != i)//그 배열이 소수아니면
{
arr[j] = -1;
}
}
}
for (int i = 0; i < N - M + 1; i++)
{
if (arr[i] == 1)
continue;
if (arr[i] != -1)
cout << arr[i] << '\n';
}
}